[Codeforces86D]Powerful array（莫队）

2019-11-08 01:44:52

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

裸莫队啊= = 但是卡常数块的大小开到600 尽量用int然后强转然后尽量避免数组寻址

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long long#define N 1000005int n,m,block,num[N],a[N],cnt[N];struct data{int l,r,id;LL ans;}q[N];LL ans;int cmp(data a,data b){ return num[a.l]<num[b.l]||(num[a.l]==num[b.l]&&num[a.r]<num[b.r]);}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&a[i]); for (int i=1;i<=m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i; block=600; for (int i=1;i<=n;++i) num[i]=(i-1)/block+1; sort(q+1,q+m+1,cmp);ans=0LL; for (int i=q[1].l;i<=q[1].r;++i) { int x=a[i],y=cnt[x]; ans-=(LL)y*y*x; ++cnt[x]; y=cnt[x]; ans+=(LL)y*y*x; }q[q[1].id].ans=ans; for (int i=2;i<=m;++i) { if (q[i].l<q[i-1].l) { for (int j=q[i-1].l-1;j>=q[i].l;--j) { int x=a[j],y=cnt[x]; ans-=(LL)y*y*x; ++cnt[x]; y=cnt[x]; ans+=(LL)y*y*x; } } else { for (int j=q[i-1].l;j<q[i].l;++j) { int x=a[j],y=cnt[x]; ans-=(LL)y*y*x; --cnt[x]; y=cnt[x]; ans+=(LL)y*y*x; } } if (q[i].r>q[i-1].r) { for (int j=q[i-1].r+1;j<=q[i].r;++j) { int x=a[j],y=cnt[x]; ans-=(LL)y*y*x; ++cnt[x]; y=cnt[x]; ans+=(LL)y*y*x; } } else { for (int j=q[i-1].r;j>q[i].r;--j) { int x=a[j],y=cnt[x]; ans-=(LL)y*y*x; --cnt[x]; y=cnt[x]; ans+=(LL)y*y*x; } } q[q[i].id].ans=ans; } for (int i=1;i<=m;++i) PRintf("%I64d/n",q[i].ans);}

上一篇：避免内存泄露及内存的规范化使用

下一篇：C# 多线程编程入门