一.莫队（静态莫队）
我们以 Luogu P3901 数列找不同 为例讲一下静态莫队
这道题是个绿题，因为数据比较弱，但真是一道良心的莫队练手题
莫队是由前国家队队长莫涛发明的
莫队算法的精髓就是通过合理地对询问排序，然后以较优的顺序暴力回答每个询问。处理完一个询问后，可以使用它的信息得到下一个询问区间的答案。 优雅的暴力
考虑这个问题：对于上面这道题，如果我们知道区间[1,5]每个数的数量，如何求出[2,6]每个数的数量
算法 1 ：暴力扫一遍。 (废话)
算法 2 ：可以在区间[1,5]的基础上，去掉位置1（即将左端点右移一位），加上位置6（即将右端点右移一位），得到区间[2,6]的答案。
很明显，算法 2 要优于算法 1 ，我们给出这部分代码：
void add(int x){
if(++t[a[x]] == 1) ++cnt;
}
void del(int x){
if(--t[a[x]] == 0) --cnt;
}
//在获取答案时
while(L<q[i].l) del(L++);
while(L>q[i].l) add(--L);
while(R<q[i].r) add(++R);
while(R>q[i].r) del(R--);
但是我们会发现如果按这样写，一种很简单的构造数据就能把时间复杂度把算法 2 也送走：先询问[1,2]，再询问[99999,100000],多重复几次就TLE了。
我们有没有办法来加速呢？
这种暴力的耗时就耗在挪动次数上，我们要让他挪动的次数尽量少。
肯定是有的，我们将询问先储存下来，再按照某种方法排序，让他减少挪动的次数，这样会变快一些。
这种方法是强行离线，然后排序，所以这样的普通莫队不能支持修改。
那么怎么排序呢？
一种解决方式是优先按照左端点排序。
这种排序的方式，保证左端点只会向右挪，但是右端点每次最坏还是可以从最前面挪到最后面，从最后面挪到最前面，这样的复杂度还是 \(O(nm)\)，是不行的。
我们的排序是要使左右端点挪动的次数尽量少，所以这里就有一种排序方法：
将序列分成 $ \sqrt{n} $ 个长度为 $ \sqrt{n} $ 的块（其实就是分块），排序第一关键字是询问的左端点所在块的编号，第二关键字是询问的右端点本身的位置，都是升序。然后我们用上面提到的“移动当前区间左右端点”的方法，按顺序求每个询问区间的答案，移动每一个询问区间左右端点可以求出下一个区间的答案。
这里先给出判断某一位置在哪个块中的代码：
int pos(int x){
if(x % (int)sqrt(n)) return x/(int)sqrt(n)+1;
return x/(int)sqrt(n);
}
这就是一般的莫队排序：
bool cmp(node a,node b){
if(pos(a.l) == pos(b.l)){
return a.r<b.r;
}
return pos(a.l)<pos(b.l);
}
但由于出题人过于毒瘤
又多出一种优化，叫做奇偶优化
按奇偶块排序。这也是比较通用的。如果区间左端点所在块不同，那么就直接按左端点从小到大排；如果相同，奇块按右端点从小到大排，偶块按右端点从大到小排。
bool cmp(node a,node b){
if(pos(a.l) == pos(b.l)){
if(pos(a.l)&1) return a.r<b.r;
else return a.r>b.r;
}
return pos(a.l)<pos(b.l);
}
可是，这样做的复杂度是什么？
大约是 \(O(n \sqrt{n})\)。
Code:
#include<bits/stdc++.h>
using namespace std;
struct node{
int l,r,id;
};
int t[100010],n,m;
node q[100010];
int a[100010],cnt;
int ans[100010];
int pos(int x){
if(x % (int)sqrt(n)) return x/(int)sqrt(n)+1;
return x/(int)sqrt(n);
}
bool cmp(node a,node b){
if(pos(a.l) == pos(b.l)){
if(pos(a.l)&1) return a.r<b.r;
else return a.r>b.r;
}
return pos(a.l)<pos(b.l);
}
void add(int x){
if(++t[a[x]] == 1) ++cnt;
}
void del(int x){
if(--t[a[x]] == 0) --cnt;
}
int main(){
cin>>n>>m;
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 L=1,R=0;
for(int i=1;i<=m;i++){
while(L<q[i].l) del(L++);
while(L>q[i].l) add(--L);
while(R<q[i].r) add(++R);
while(R>q[i].r) del(R--);
ans[q[i].id] = (cnt == q[i].r-q[i].l+1) ? 1 : 0;
}
for(int i=1;i<=m;i++){
printf(ans[i] ? "Yes\n" : "No\n");
}
return 0;
}
二、带修莫队
特点
- 用于离线处理区间问题
- 仅含单点修改
- 能 \(O(1)\) 转移区间（和普通莫队一样）
- 分块的每一块的大小是 \(n^{\frac{2}{3}}\)
- 复杂度 \(O(n^{\frac{5}{3}})\)
带修改的莫队的询问排序方法为：
- 第一关键字：左端点所在块编号，从小到大排序。
- 第二关键字：右端点所在块编号，从小到大排序。
- 第三关键字：经历的修改次数。也可以说是询问的先后，先询问的排前面。
对于前后两个区间的转移：
设当前询问为 \(a\)，下一个询问为 \(b\)，我们已知 \(a\)，要求 \(b\)。
首先我们像普通莫队一样转移左右端点。
这时候我们可能会发现 \(a\) 和 \(b\) 的经历的修改次数不同！
怎么办呢？
然而，莫队就是个优雅的暴力。
假如 \(a\) 较 \(b\) 少修改了 \(p\) 次，那我们就把这 \(p\) 次修改一个一个从前往后暴力地加上去。假如 \(a\) 较 \(b\) 多修改了 \(q\) 次，那我们就把这 \(q\) 次修改从后往前还原掉。
具体代码与普通莫队大同小异，这里不再给出。
例题：P1903 [国家集训队]数颜色 / 维护队列