P2709 小B的询问

*原题链接*

非常简单的莫队板子题，让我们求出区间[l,r]中每个数出现次数的平方和，设枚举到,原来答案是res，如果加上后，则原来的变为，即res相比原来加上，删除同理。知道如何维护一个数的添加和删除后，剩下的套莫队板子就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;int n,m,k,t,a[N],ans[N],pos[N],cnt[N],res;struct node{int l,r,id;
}que[N];bool cmp(node a,node b){if(pos[a.l]==pos[b.l]) return a.r<b.r;return a.l<b.l;
}void del(int x){res+=-2*cnt[a[x]]+1;cnt[a[x]]--;
}void add(int x){res+=2*cnt[a[x]]+1;cnt[a[x]]++;
}int main(){cin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>a[i];t=sqrt(n);for(int i=1;i<=n;i++) pos[i]=(i-1)/t+1;for(int i=1;i<=m;i++) cin>>que[i].l>>que[i].r,que[i].id=i;sort(que+1,que+1+m,cmp);for(int i=1,l=1,r=0;i<=m;i++){while(l<que[i].l) del(l++);while(r>que[i].r) del(r--);while(l>que[i].l) add(--l);while(r<que[i].r) add(++r);ans[que[i].id]=res;}for(int i=1;i<=m;i++) cout<<ans[i]<<endl;return 0;
}