hiho 1553区间统计 莫队算法+分块思想

题意：a数组，q次查询，[l,r]区间内不同数的个数的K次方的和

思路：

考虑如果没有K次可以随便莽，这里主要有k这个限定条件。。这里提供一个O（n sqrt(n) logn）的方法，在莫队的过程中，我们不直接计算答案。在这里引入分块的思想。通过维护两个数组就，一个是x的出现次数，一个是出现y次的数有几个。那么分两种情况，一种是出现次数小于根号N的，一种是大于根号N的。又因为大于根号N的出现次数的数不超过根号N个，所以接下来就有了解决方案。每次莫队维护这两个数组以及一个set维护出现次数大于根号N的数。之后每次结束后分两类暴力解决。按之前的分析，单次最坏为sqrt n*logn 。故总时间复杂度是nsqrtn+nsqrtnlogn

PS。感谢zyyyyy菊苣提供代码参考，%%%%。

代码：

#include<bits/stdc++.h>
using namespace std;
#define MEM(a,b) memset(a,b,sizeof(a))
#define bug puts("bug");
#define PB push_back
#define MP make_pair
#define X first
#define Y second
typedef unsigned long long ll;
const int maxn=1e5+10;
const int mod=1000000007;
using namespace std;
struct qnode{
    int r,l,num,id,k;
    qnode(int L=0,int R=0,int i=0,int nm=0,int kk=0)
    :r(R),l(L),id(i),num(nm),k(kk){};
}Q[maxn];
bool cmp(qnode q1,qnode q2){
    return q1.num!=q2.num?q1.num<q2.num:q1.r<q2.r;
}
int a[maxn],x,y,z,n,m,t;
ll num[maxn],cnt[maxn],po[maxn][105],ans[maxn];
ll ret,l,r,big;
unordered_set<int> S;
void add(int x){
    --cnt[num[x]];
    ++cnt[++num[x]];
    if(num[x]==big) S.insert(x);
}

void del(int x){
    if(num[x]==big) S.erase(x);
    --cnt[num[x]];
    ++cnt[--num[x]];
}

int main(){
    for(int i=1;i<=100000;i++){
        po[i][0]=1;
        for(int j=1;j<=100;j++)
            po[i][j]=(po[i][j-1]*i)%mod;
    }
    scanf("%d",&t);
    while(t--){
        MEM(num,0);MEM(cnt,0);S.clear();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        big=sqrt(n);
        for(int i=1;i<=m;++i)
            scanf("%d%d%d",&x,&y,&z),Q[i]=(qnode(x,y,i,x/big,z));
        sort(Q+1,Q+1+m,cmp);
        l=1,r=0;
        for(int i=1;i<=m;i++){
            ret=0;
            while(Q[i].r>r)add(a[++r]);
            while(Q[i].l<l)add(a[--l]);
            while(Q[i].r<r)del(a[r--]);
            while(Q[i].l>l)del(a[l++]);
            for(int j=1;j<big;j++) ret=(ret+(cnt[j]*po[j][Q[i].k])%mod)%mod;
            for(int x:S) ret=(ret+po[num[x]][Q[i].k])%mod;
            ans[Q[i].id]=ret;
        }
        for(int i=1;i<=m;i++) printf("%lld
",ans[i]);
    }
    return 0;
}