前往：我自己搭建的博客
题目
洛谷P2709小B的询问
题解
莫队算法要求询问可以离线，并且要求被询问的区间信息便于从邻近区间转移。它是一种优化的暴力，通过将询问进行特殊的排序（方法有很多种），使得相似的询问排在一起，可以批量处理。被询问区间的排序方式：需要用到分块思想（将一段序列分成几段），所有被询问区间的左端点所在的分块的编号递增（即被询问区间的左端点大体呈递增趋势），每个分块内的区间右端点单调，且相邻分块的单调性相反（即被询问区间的右端点大体呈波浪形）。分块大小和排序方式的原因玄学，无法理论上求最优方式，只能测试。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e4+5;
int n,m,k,block;
ll ans;
int a[maxn],belong[maxn],sum[maxn]; //sum[i]表示数字i出现的次数,belong[i]表示位置i属于的分块
struct ask{int l,r,id; ll ans;}q[maxn];
inline int read()
{
int s=0; char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
inline bool cmp1(const ask &x,const ask &y)
{
return belong[x.l]^belong[y.l] ? belong[x.l]<belong[y.l] : belong[x.l]&1 ? x.r>y.r : x.r<y.r;
}
inline bool cmp2(const ask &x,const ask &y) {return x.id<y.id;}
inline void add(int x) //向当前区间中加入一个数字x
{
ans-=(ll)sum[x]*sum[x];
sum[x]++;
ans+=(ll)sum[x]*sum[x];
}
inline void del(int x) //从当前区间中删掉一个数字x
{
ans-=(ll)sum[x]*sum[x];
sum[x]--;
ans+=(ll)sum[x]*sum[x];
}
int main()
{
n=read(),m=read(),k=read(); block=n/sqrt(m*2/3);
for(int i=1;i<=n;i++) a[i]=read(),belong[i]=(i-1)/block+1;
for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1,cmp1); int l=1,r=0;
for(int i=1;i<=m;i++)
{
while(l>q[i].l) add(a[--l]);
while(l<q[i].l) del(a[l++]);
while(r<q[i].r) add(a[++r]);
while(r>q[i].r) del(a[r--]);
q[i].ans=ans;
}
sort(q+1,q+m+1,cmp2);
for(int i=1;i<=m;i++) printf("%lld\n",q[i].ans);
return 0;
}
