修改一下莫队的增加与修改即可。
#include <bits/stdc++.h>
using namespace std;
int n,a[50010],m,p;
int L=1,R=0,bl;
struct node {
int l,r,num;
} q[200010];
bool cmp(node a,node b) {
return (a.l/bl)==(b.l/bl)?a.r<b.r:(a.l/bl)<(b.l/bl);
}
int cnt[1000010],sum;
void add(int x) {
cnt[x]++;
sum+=cnt[x]*cnt[x]-(cnt[x]-1)*(cnt[x]-1);
}
void del(int x) {
cnt[x]--;
sum-=(cnt[x]+1)*(cnt[x]+1)-cnt[x]*cnt[x];
}//如上为莫队的修改操作，其实就改了一点点
int ans[200010];
int main() {
scanf("%d %d %*d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
//scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d %d",&q[i].l,&q[i].r),q[i].num=i;
bl=sqrt(n);
//printf("%d
",bl);
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++) {
//printf("now do %d
",q[i].num);
while(R<q[i].r) add(a[++R]);
while(R>q[i].r) del(a[R--]);
while(L<q[i].l) del(a[L++]);
while(L>q[i].l) add(a[--L]);
ans[q[i].num]=sum;
}
for(int i=1;i<=m;i++)
printf("%d
",ans[i]);
return 0;
}