题目链接：

题意：

给一段长度为N的序列，每次询问l-r（l和r和上一次询问的答案有关）内 不同的数的 出现次数的次方 的和。强制在线

题解：

这里贴个达哥的题解：

大体思路就是，把n个数分成sqrt（n）块，每块sqrt(n)个数，然后求出任意两块i到j（包含第i块和第j块）的ans，对于每次询问l和r，找到刚好包含l和r的一段连续的块，因为我们已经知道了这段连续块的答案，所以只要再去掉两段多出来的一部分，就好了。

为了得到任意两块间的答案G[i][j],我们可以枚举每个块的起点，然后for到最后，暴力一边，就好了，

对于多出来的一部分，我们只要知道这一部分里的数，在包含它的连续块中已经出现了几次，然后就可以很容易地更新答案了。于是我们可以先预处理出一个后缀和cnt[i][j]:表示从第i块开始，第j小的数出现了多少次，然后，对于每次询问q，我们 只要 只要 只要 （后缀和减一下）找到这一部分里的数在连续的块中出现了次数就好了，别的数就算了，都找的话，肯定超时。

之前还要预处理各种数次方的结果，还要排序，去重。

cnt[i][j]:从第i块开始到最后第j小的数出现的次数  

pos[i]:在A中下标为i的数是第几小  

1 #include
      
        2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 typedef long long ll; 5  6 const int N=5e4+7,P=1e9+7; 7  8 int sqr,n,m,l,r,len,t,pos[N],cnt[240][N]; 9 ll A[N],a[N],num[N],vis[N];10 vector
       
        v[N];//第i小的数的j次方11 ll G[240][240];//块i到j的答案12 13 int T_T(int l,int r)14 {15     int L=l/sqr,R=r/sqr;16     ll ans=G[L][R];17     int LL=L*sqr,RR=min(n-1,(R+1)*sqr-1);18     F(i,LL,l-1)num[pos[i]]=cnt[L][pos[i]]-cnt[R+1][pos[i]];19     F(i,r+1,RR)num[pos[i]]=cnt[L][pos[i]]-cnt[R+1][pos[i]];20     while(LL
        
         r)27     {28         ans-=v[pos[RR]][num[pos[RR]]];29         ans+=v[pos[RR]][--num[pos[RR]]];30         RR--;31     }32     return (ans%P+P)%P;33 }34 35 int main()36 {37     scanf("%d",&t);38     while(t--)39     {40         scanf("%d%d",&n,&m);41         F(i,0,n-1)scanf("%lld",a+i),A[i]=a[i];42         sort(a,a+n),len=unique(a,a+n)-a;43         F(i,0,len-1)v[i].clear(),v[i].push_back(0),vis[i]=0;44         F(i,0,n-1)vis[pos[i]=lower_bound(a,a+len,A[i])-a]++;45         F(i,0,len-1)46         {47             ll p=1;48             F(j,1,vis[i])v[i].push_back(p=p*a[i]%P);49         }50         sqr=sqrt(n+0.5);51         memset(cnt,0,sizeof(cnt));52         for(int i=0;i*sqr
         
          r)l^=r,r^=l,l^=r;71             printf("%d\n",la=T_T(l,r));72         }73     }74     return 0;75 }