P2709 小B的询问
莫队算法，弄两个指针乱搞即可
这应该是基础莫队了吧
$x^2$可以拆成$((x-1)+1)^2$，也就是$(x-1)^2+1^2+2\times (x-1)$，那么如果一个数字出现的次数修改$-1$，那么$ans-=1+2\times (sum[a[pos]]-1)$，$sum[a[pos]]$表示出现在$pos$位置上的数出现的次数。
反之同理。。。
#include<bits/stdc++.h> #define N 500000
using namespace std; int n,m,k,bl,v[N],ans,sum[N]; struct node{
int l,r,id,an;
}e[N]; bool cmp(node A,node B){
return A.l/bl==B.l/bl ? A.r<B.r : A.l<B.l;
} bool ccmp(node A,node B){
return A.id<B.id;
} void remove(int x){
ans-=+*(sum[v[x]]-),sum[v[x]]--;
} void insert(int x){
ans+=+*(sum[v[x]]),sum[v[x]]++;
} int main()
{
scanf("%d%d%d",&n,&m,&k);
bl=sqrt(n);
for(int i=;i<=n;i++) scanf("%d",&v[i]);
for(int i=;i<=m;i++) scanf("%d%d",&e[i].l,&e[i].r),e[i].id=i;
sort(e+,e++m,cmp); int curL=,curR=;
for(int i=;i<=m;i++){
int L=e[i].l,R=e[i].r;
while(curL<L) remove(curL++);
while(curL>L) insert(--curL);
while(curR>R) remove(curR--);
while(curR<R) insert(++curR);
e[i].an=ans;
} sort(e+,e++m,ccmp);
for(int i=;i<=m;i++) printf("%d\n",e[i].an-); return ;
}