题目: https://www.lydsy.com/JudgeOnline/problem.PHP?id=3781
就是莫队, 左端点分块排序, 块内按右端点排序, 然后直接做即可.
代码如下:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- typedef long long ll;
- int const xn=5e4+5;
- int n,m,k,cnt[xn],d[xn],blk[xn],a[xn];
- ll sum,ans[xn];
- struct N{int l,r,id;}q[xn];
- bool cmp(N x,N y){return blk[x.l]==blk[y.l]?x.r<y.r:blk[x.l]<blk[y.l];}
- int rd()
- {
- int ret=0,f=1; char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}
- while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
- return f?ret:-ret;
- }
- void add(int ps)
- {
- int x=a[ps];
- sum-=(ll)cnt[x]*cnt[x];
- cnt[x]++;
- sum+=(ll)cnt[x]*cnt[x];
- }
- void del(int ps)
- {
- int x=a[ps];
- sum-=(ll)cnt[x]*cnt[x];
- cnt[x]--;
- sum+=(ll)cnt[x]*cnt[x];
- }
- int main()
- {
- n=rd(); m=rd(); k=rd(); int bs=sqrt(n);
- for(int i=1;i<=n;i++)a[i]=rd(),blk[i]=(i-1)/bs+1;
- for(int i=1;i<=m;i++)q[i].l=rd(),q[i].r=rd(),q[i].id=i;
- sort(q+1,q+m+1,cmp); add(1);
- for(int i=1,l=1,r=1;i<=m;i++)
- {
- int ql=q[i].l,qr=q[i].r;
- while(l<ql)del(l),l++;
- while(l>ql)l--,add(l);
- while(r<qr)r++,add(r);
- while(r>qr)del(r),r--;
- ans[q[i].id]=sum;
- }
- for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2795800.html