P2709 小B的询问 莫队
只要能想出(O(1))的方式转移([l,r])，莫队就不难了。此题求区间(sum_{i=1}^kcnt[i]^2)，那我们就(O(1))更新就好了，先减去原来的贡献，更新cnt[]再加上现在的贡献，这样就更新完了。
注意：莫队小心初始化，直接l=0,r=0等可能会炸。
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 50005
using namespace std;
int n,m,k,a[MAXN],block;
int cnt[MAXN],sum,ans[MAXN];
struct nod{
int l,r,bid,qid;
} q[MAXN];
inline bool cmp(nod a, nod b){
return ((a.bid^b.bid)?(a.l<b.l):((a.bid&1)?a.r<b.r:a.r>b.r));
}
inline int my_sqr(int x){
return x*x;
}
inline int read(){
char ch=getchar();int s=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s;
}
inline void add(int x){
sum-=my_sqr(cnt[a[x]]);
++cnt[a[x]];
sum+=my_sqr(cnt[a[x]]);
}
inline void del(int x){
sum-=my_sqr(cnt[a[x]]);
--cnt[a[x]];
sum+=my_sqr(cnt[a[x]]);
}
int main()
{
n=read(),m=read(),k=read();
block=n/sqrt(m*2/3);
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=m;++i){
q[i].l=read(), q[i].r=read();
q[i].qid=i;
q[i].bid=q[i].l/block;
}
sort(q+1, q+1+m, cmp);
int l=1,r=1;
sum=1;cnt[a[1]]=1;
for(int i=1;i<=m;++i){
int ql=q[i].l,qr=q[i].r;
while(l<ql) del(l++);
while(l>ql) add(--l);
while(r<qr) add(++r);
while(r>qr) del(r--);
ans[q[i].qid]=sum;
}
for(int i=1;i<=m;++i) printf("%d
", ans[i]);
return 0;
}