CF——powerful array莫队模版

极大部分借鉴了此链接
至今不太理解莫队的奇偶排序和分块思想带来的超大变化……
先整理模版再说

#include<iostream>
#include<cmath>
#include<set>
#include<map>
#include<algorithm>
#include<cstdio>
using namespace std;
const int NN=1e6+5;
struct Node
{int L,R;int id;
};
Node q[NN];//查询区间的值
int a[NN];//原数组
int block;//分块大小
long long ans;//查询区间结果
long long cnt[NN*2];//表示数据出现的次数
long long res[NN];//根据查询编号存结果bool cmp(Node aa,Node bb)//玄学奇偶排序
{return (aa.L/block)^(bb.L/block)?aa.L<bb.L:(((aa.L/block)&1)?aa.R<bb.R:aa.R>bb.R);
}
void add(int x)//增加操作，根据题目做改变
{
// ans-=cnt[a[x]]*cnt[a[x]]*a[x];
// cnt[a[x]]++;
// ans+=cnt[a[x]]*cnt[a[x]]*a[x];ans+=(2*cnt[a[x]]+1)*a[x];cnt[a[x]]++;
}
void del(int x)//删除操作，根据题目做改变
{
// ans-=cnt[a[x]]*cnt[a[x]]*a[x];
// cnt[a[x]]--;
// ans+=cnt[a[x]]*cnt[a[x]]*a[x];cnt[a[x]]--;ans-=(2*cnt[a[x]]+1)*a[x];
}
int main()
{int n,m;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=sqrt(m*2/3.0);//分块大小sort(q+1,q+m+1,cmp);//对询问区间进行排序int lft=1,rht=0;//左右指针for(int i=1; i<=m; i++){int ql=q[i].L,qr=q[i].R;while(lft>ql)add(--lft);//初始左边比查询的左边大了，加左边while(rht<qr)add(++rht);//初始右边比查询的右边小了，加右边while(lft<ql)del(lft++);//初始左边比查询的左边小了，删左边while(rht>qr)del(rht--);//初始右边比查询的右边大了，删右边res[q[i].id]=ans;//存结果}for(int i=1;i<=m;i++){printf("%lld\n",res[i]);}return 0;
}