OJ题号：BZOJ3781、洛谷2709
思路：
根据平方和公式，$(a+b)^2=a^2+2ab+b^2$，即当$c_i$增加$1$时，新的答案增加$2C_i+1$，减少时亦同。莫队求解即可。
1 #include<cstdio> 2 #include<cctype> 3 #include<cmath> 4 #include<algorithm> 5 inline int getint() { 6 char ch; 7 while(!isdigit(ch=getchar())); 8 int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 int base; 13 struct Que { 14 int l,r,id; 15 bool operator < (const Que &x) const { 16 return (r/base<x.r/base)?true:((r/base==x.r/base)?(l<x.l):false); 17 } 18 }; 19 const int K=50001; 20 int cnt[K]={0},Ans=0; 21 inline void inc(const int x) { 22 Ans+=cnt[x]<<1|1; 23 cnt[x]++; 24 } 25 inline void dec(const int x) { 26 cnt[x]--; 27 Ans-=cnt[x]<<1|1; 28 } 29 int main() { 30 int n=getint(),m=getint();getint(); 31 base=(int)sqrt(n); 32 int a[n]; 33 for(int i=0;i<n;i++) a[i]=getint(); 34 Que q[m]; 35 for(int i=0;i<m;i++) { 36 q[i].l=getint()-1; 37 q[i].r=getint()-1; 38 q[i].id=i; 39 } 40 std::sort(&q[0],&q[m]); 41 int ans[m]; 42 for(int i=0,l=0,r=-1;i<m;i++) { 43 while(r<q[i].r) inc(a[++r]); 44 while(r>q[i].r) dec(a[r--]); 45 while(l<q[i].l) dec(a[l++]); 46 while(l>q[i].l) inc(a[--l]); 47 ans[q[i].id]=Ans; 48 } 49 for(int i=0;i<m;i++) printf("%d ",ans[i]); 50 return 0; 51 }