一、概念
莫队是一种应用于离线询问的优美暴力算法。它是主要思想是让区间的左端点和右端点移动的距离加起来最短。
二、实现
假设现在有这样一串序列：\(1,1,4,5,1,4\)，我们现在要求询问区间内的 \(1\) 的出现次数。
如果我们现在已经统计到了区间 \((2,3)\)，现在询问 \((1,5)\)。
现在的答案是这样的：
我们发现现在的左端点 \(x=2\) 在询问的左端点的右边，所以我们将当前左端点向左移一位。现在维护的区间 \([1,3]\) 有两个 \(1\) 了。
我们又发现现在的右端点 \(y=3\) 在询问的右端点左边，所以我们将当前右端点向右移一位。现在维护的区间 \([1,4]\) 还是有两个 \(1\)。
这时候的右端点还是在询问的右端点。所以我们再将右端点向右移一位。现在维护的区间 \([1,5]\) 有三个 \(1\) 了。
这时候访问到的区间与询问的区间完全一样，我们就可以存储答案了。
这就是莫队的思想了（。你会发现这十分的像暴力，的确如此。但是为了保证时间复杂度，我们要引入分块的思想。先将 \(l\) 按照所在块的编号排序，在每个块中，再按 \(r\) 的大小排序。
这样的话我们发现在每个块中，\(r\) 最多会移 \(n\) 次，每换一次块，就可能多移 \(n\) 次。同时，每次询问 \(l\) 都可能移动 \(size\) 次。所以时间复杂度应该为 \(O(n\times num+m\times size)=O(\frac{n^2}{size}+m\times size)\)。
我们发现每换一次块，\(r\) 可能会从最右边跑到最左边，这显然不优。所以我们考虑奇偶性优化，如果第一个块的编号为偶数，那么块的编号为偶数就将 \(r\) 升序排序，为奇数就将 \(r\) 降序排序。如果第一个块的编号为奇数，那么就都反过来。
三、代码
感觉比较板的题是这题：小B的询问
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;
int n,m,k;
int a[N];
int buc[N];
int ansi[N];
int T;
int sum;
struct node{
int l,r,id;
}q[N];
bool cmp(node x,node y){
if(x.l/T==y.l/T) return x.r<y.r;
return x.l<y.l;
}
void add(int x){
sum-=buc[a[x]]*buc[a[x]];
buc[a[x]]++;
sum+=buc[a[x]]*buc[a[x]];
}
void del(int x){
sum-=buc[a[x]]*buc[a[x]];
buc[a[x]]--;
sum+=buc[a[x]]*buc[a[x]];
}
signed main(){
ios::sync_with_stdio(false);
cin>>n>>m>>k;
T=sqrt(n);
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=m;++i){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int x=1,y=0;
for(int i=1;i<=m;++i){
int qx=q[i].l,qy=q[i].r;
while(x>qx){
x--;
add(x);
}
while(y<qy){
y++;
add(y);
}
while(x<qx){
del(x);
x++;
}
while(y>qy){
del(y);
y--;
}
ansi[q[i].id]=sum;
}
for(int i=1;i<=m;++i) cout<<ansi[i]<<"\n";
return 0;
}
四、例题
等我咕一下（