[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)