感谢莫涛大队长的算法(不该乱奶)
题目翻译给得很有良心，概括得很全面
由于没有修改，可以离线，很容易想到莫队
我们考虑如何左右移动指针 l 和 r
考虑我们现在已经得出了一个当前 l 、 r 的答案——sum
在该区间中 ，值为 x 的数 出现的个数 被 c[x] 统计
假设我们现在要加入一个数 a[i]
很明显 我们需要统计 c[a[i]] 在得到 a[i] 后 对答案的贡献
我介绍两种方法
1.运用完全平方公式 (a+b)^2 = a^2 + 2ab + b^2
对于 a[i] 出现的次数 c[a[i]]
它原本对答案的贡献为 c[a[i]]^2
现在它增加为 c[a[i]]+1
他对答案的贡献改为 (c[a[i]]+1)^2
展开得 c[a[i]]^2 + 2*c[a[i]] + 1
由于我们现在只统计了 c[a[i]]^2
所以 还要加上 2*c[a[[i]] + 1 就行了
2.既然原来的 c[a[i]] 已经过时了
那么就直接将他的贡献减去
加入 c[a[i]]+1 对答案的贡献两种方法都是 O(1) ，可以采用 ，个人认为第二种更好理解
剩下的就是一些普遍的东西了
先读入 ， 再奇偶性排序 ， 然后跑莫队
代码也不长 1.1KB 左右
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #define MAXN 1000005 #define LL long long using namespace std; LL sum,a[MAXN],ans[MAXN],c[MAXN]; int n,m,L,R,pos[MAXN]; struct ques { int l,r; int id; }f[MAXN]; bool cmp(const ques k,const ques t) { if (pos[k.l]==pos[t.l]) return k.r<t.r; return k.l<t.l; } void add(int x) { sum-=c[a[x]]*c[a[x]]*a[x]; c[a[x]]++; sum+=c[a[x]]*c[a[x]]*a[x]; } void del(int x) { sum-=c[a[x]]*c[a[x]]*a[x]; c[a[x]]--; sum+=c[a[x]]*c[a[x]]*a[x]; } void que(int l,int r) { while (L<l) del(L++); while (L>l) add(--L); while (R<r) add(++R); while (R>r) del(R--); return; } int main() { scanf("%d %d",&n,&m); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); int len=sqrt(n); for (int i=1;i<=n;i++) pos[i]=(i-1)/len+1; for (int i=1;i<=m;i++) { scanf("%d %d",&f[i].l,&f[i].r); f[i].id=i; } sort(f+1,f+m+1,cmp); L=1; R=0; sum=0; for (int i=1;i<=m;i++) { que(f[i].l,f[i].r); ans[f[i].id]=sum; } for (int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; }
原文：https://www.cnblogs.com/maowuyou/p/11913920.html