大致题意： 有一个长度为\(N\)的序列，每个数字在\(1\sim K\)之间，有\(M\)个询问，每个询问给你一个区间，让你求出\(\sum_{i=1}^K c(i)^2\)，其中\(c(i)\)表示数字\(i\)在该区间内的出现次数。

莫队算法

显然，这题可以用来做，而这题本身就是莫队算法的一道模板题。

代码

#include
    
     #define N 50000#define M 50000using namespace std;int n,Q,k,a[N+5],pos[N+5],cnt[N+5],ans[M+5];struct Query{    int l,r,pos;}q[M+5];inline char tc(){    static char ff[100000],*A=ff,*B=ff;    return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;}inline void read(int &x){    x=0;char ch;    while(!isdigit(ch=tc()));    while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));}inline void write(int x){    if(x>9) write(x/10);    putchar(x%10+'0');}bool cmp(Query x,Query y){    return pos[x.l]
     
      
       y.r));}int main(){    register int i;    read(n),read(Q),read(k);    for(i=1;i<=n;++i) read(a[i]),pos[i]=(i-1)/sqrt(n)+1;//边读入，边将序列分块    for(i=1;i<=Q;++i) read(q[i].l),read(q[i].r),q[i].pos=i;//存储下来每一个询问    sort(q+1,q+Q+1,cmp);//将询问以l所在的块为第一关键字，r的值为第二关键字sort一遍    int L=q[1].l,R=q[1].r;//将L指针和R指针预处理为指向第一个询问的l和r    for(i=q[1].l;i<=q[1].r;++i)//暴力求解第一个询问        ans[q[1].pos]-=cnt[a[i]]*cnt[a[i]],++cnt[a[i]],ans[q[1].pos]+=cnt[a[i]]*cnt[a[i]];    for(i=2;i<=Q;++i)//对每一个询问依次求解    {        ans[q[i].pos]=ans[q[i-1].pos];        while(L
       
        q[i].l) --L,ans[q[i].pos]-=cnt[a[L]]*cnt[a[L]],++cnt[a[L]],ans[q[i].pos]+=cnt[a[L]]*cnt[a[L]];//若L大于当前询问的l，则将L减1，并更新ans（注意，这里改变L值和更新ans的顺序与上一个操作不同）        while(R>q[i].r) ans[q[i].pos]-=cnt[a[R]]*cnt[a[R]],--cnt[a[R]],ans[q[i].pos]+=cnt[a[R]]*cnt[a[R]],--R;//类似于上面的操作        while(R