【传送门：BZOJ3781】
简要题意：
给出n个数a[i]，有k种数，m个询问，每个询问输入l,r，输出$sum_{k}^{i=1}c[i]^2$，c[i]表示数字i在l到r中出现的次数
题解：
莫队（非常明显）
直接分块，设sum[i]为当前l到r之间数字为i出现的个数，对于处理l和r的位置，只要将sum处理一下，把ans也处理一下就行了
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; int a[51000]; struct qn { int l,r,id; LL d; }q[51000]; int bk[51000]; bool cmp(qn n1,qn n2) { return bk[n1.l]==bk[n2.l]?n1.r<n2.r:bk[n1.l]<bk[n2.l]; } bool cmpd(qn n1,qn n2) { return n1.id<n2.id; } LL sum[51000],ans; void update(int x,int ad) { ans-=sum[a[x]]*sum[a[x]]; sum[a[x]]+=ad; ans+=sum[a[x]]*sum[a[x]]; } int main() { int n,m,k; scanf("%d%d%d",&n,&m,&k); int block=int(sqrt(n)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); bk[i]=(i-1)/block+1; } for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+m+1,cmp); int l=1,r=0; ans=0; memset(sum,0,sizeof(sum)); for(int i=1;i<=m;i++) { while(l<q[i].l){update(l,-1);l++;} while(l>q[i].l){update(l-1,1);l--;} while(r<q[i].r){update(r+1,1);r++;} while(r>q[i].r){update(r,-1);r--;} q[i].d=ans; } sort(q+1,q+m+1,cmpd); for(int i=1;i<=m;i++) printf("%lld ",q[i].d); return 0; }