挺裸的莫队,然而我用lld输出T掉了???改成I64d输出就过了???有毒。
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define ll long long #define N 200010 int n,m,a[N],f[1000005],block; bool vis[N]; ll ans=0,ANS[N]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } struct query{ int l,r,id,block; }q[N]; inline bool cmp(query x,query y){ return x.block==y.block?x.r<y.r:x.block<y.block; } inline void update(int x){ ans-=(ll)f[a[x]]*f[a[x]]*a[x]; if(vis[x]) f[a[x]]--; else f[a[x]]++; ans+=(ll)f[a[x]]*f[a[x]]*a[x]; vis[x]^=1; } int main(){ // freopen("a.in","r",stdin); n=read();m=read();block=sqrt(n); for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<=m;++i){ q[i].l=read();q[i].r=read();q[i].id=i; q[i].block=(q[i].l-1)/block; }std::sort(q+1,q+m+1,cmp);int l=1,r=0; for(int i=1;i<=m;++i){ if(q[i].l==q[i].r){ ANS[q[i].id]=a[q[i].l];continue; } for(;l<q[i].l;++l) update(l); for(;l>q[i].l;--l) update(l-1); for(;r<q[i].r;++r) update(r+1); for(;r>q[i].r;--r) update(r); ANS[q[i].id]=ans; } for(int i=1;i<=m;++i) printf("%I64d\n",ANS[i]); return 0; }