6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6
6 //在区间[1..4]]之间，1出现了2次，2和3分别出现1次，于是结果=4+1+1=6
9
5
2
1莫队算法
2因为是求出Sigma(c(i)^2)的值，所以在模板上要改进一下
3可知当c(i)++,总和加上c(i+1)^-c(i)^=c(i)*2+1，就有了代码中的ans+=num[x]*2+1;(如果在最后再枚举一遍会超时，所以要在线统计，c(i)--的情况读者可以先自行推导再看代码）
#include<bits/stdc++.h> using namespace std; long long n,m,cnt[200000],ans,k,num[1000001],l,r,anss[200001]; struct data { long long ll,rr,num; }a[200001]; bool cmp(data c,data d) { long long bol=sqrt(n); if(c.ll/bol==d.ll/bol) return c.rr<d.rr; else return c.ll/bol<d.ll/bol; }//莫队排序 void add(long long xx){ long long x=cnt[xx]; ans+=num[x]*2+1; num[x]++; } void del(long long xx){ long long x=cnt[xx]; if(num[x]-1>=0) ans=ans-num[x]*2+1, num[x]--; } void dowork(long long x){ while(l>a[x].ll) add(--l); while(r<a[x].rr) add(++r); while(l<a[x].ll) del(l++); while(r>a[x].rr) del(r--); anss[a[x].num]=ans; }//莫队板子 int main(){ cin>>n>>m>>k; for(long long i=1;i<=n;i++){ scanf("%lld",&cnt[i]); } for(long long i=1;i<=m;i++){ scanf("%lld%lld",&a[i].ll,&a[i].rr); a[i].num=i; } sort(a+1,a+m+1,cmp); for(long long i=1;i<=m;i++){ dowork(i); } for(long long i=1;i<=m;i++) printf("%lld\n",anss[i]); }
--
原文：https://www.cnblogs.com/cwjr/p/12943301.html