0 前言
前置知识：
-
会打暴力。 -
简单的分块或根号思想。
二次离线莫队不会，就不写了。
1 普通莫队
不妨直接上一个例题来看看，通过题目来直接引入莫队：题目链接。
题意：给定一个长度为 \(n\) 的数列 \(n\)，\(m\) 次询问区间 \([l,r]\) 中的不同数字数。
我们不妨设置两个指针 \(l,r\)，表示询问区间的左右端点，初始令 \(l=1,r=0\)。
对于每次询问，暴力做法就是直接开一个桶，然后每次把 \(l,r\) 指针移动到对应的区间，顺便更新下桶，期间把答案统计出来就可以了。但是这样的时间复杂度是 \(O(nm)\) 的，无法通过。
不过这一步十分重要，先放个代码大家理解下：
void Add(int x){ //将数加入桶中
if(!cnt[a[x]]) now++;
cnt[a[x]]++;
}
void Del(int x){ //将数从桶中删除
cnt[a[x]]--;
if(!cnt[a[x]]) now--;
}
void Main(){
read(n);For(i,1,n) read(a[i]);
read(m);For(i,1,m) read(q[i].l,q[i].r),q[i].id=i;
int l=1,r=0;
For(i,1,m){
while(l>q[i].l) Add(--l); //移动l，r指针到对应区间
while(r<q[i].r) Add(++r);
while(l<q[i].l) Del(l++);
while(r>q[i].r) Del(r--);
ans[q[i].id]=now;
}
For(i,1,m) printf("%d\n",ans[i]);
}
考虑上述做法复杂度高的原因：我们的 \(l,r\) 指针每次询问的移动次数最高是可以到达 \(O(n)\) 的（比如上次 \(l\) 是 \(1\)，这次 \(l\) 是 \(n\)）。而莫队的核心思想就在于，通过分块和排序的方式来降低指针的移动次数。
具体怎么做呢？我们考虑对原序列进行分块：将原序列分为 \(\sqrt n\) 块，每块的长度为 \(\sqrt n\)（理论上块长取 \(\frac{n}{\sqrt m}\) 最优，但是差别不大，见下文的复杂度证明）。然后，将所有的询问离线下来，并按照如下方式排序：对于每个询问，优先按照左端点所在的块的编号进行排序，如果左端点所在块的编号相同就按照右端点排序。
然后再套用我们上面的暴力方法做即可。
这样复杂度变了多少呢？直接省掉了一个根号！
接下来我们不妨对其复杂度进行证明（下文中记块长为 \(B\)）：
update on 2023/5/1：在省集听了 lxl 的讲解之后，才知道我莫队的复杂度一直是记错的。
左指针的移动：假如下一个左端点在当前块内，由于块的大小为 \(B\)，那么此时左指针移动的复杂度就是 \(O(B)\)；假如下一个左端点和当前不在同一个块内，那么左指针最多只会跑到下一个块内，复杂度也是 \(O(B)\)。综上，左指针每次移动的复杂度不会超过 \(O(B)\)，总复杂度不会超过 \(O(mB)\)。
右指针的移动：对于每一个块，右指针单调递增，因此每一个块内右指针移动的复杂度为 \(O(n)\)，而总共有 \(\frac{n}{B}\) 个块，因此右指针移动总复杂度不会超过 \(O(\frac{n^2}{B})\)。
总复杂度为 \(O(mB+\frac{n^2}{B})\)，根据基本不等式，令 \(mB=\frac{n^2}{B}\)，可以解得 \(B=\frac{n}{\sqrt m}\)，代入可得总复杂度为 \(O(m\sqrt n)\)。
说了这么多，代码终于能端上来了。
struct Query{
int id,l,r;
}q[N];
int n,m,now,a[N],bl[N],cnt[N],ans[N];
bool cmp(const Query &a,const Query &b){
if(bl[a.l]==bl[b.l]) return a.r<b.r; //分块后排序
return bl[a.l]<bl[b.l];
}
void Add(int x){ //将数加入桶
if(!cnt[a[x]]) now++;
cnt[a[x]]++;
}
void Del(int x){ //将数从桶中删除
cnt[a[x]]--;
if(!cnt[a[x]]) now--;
}
void Main(){
read(n);For(i,1,n) read(a[i]);
read(m);For(i,1,m) read(q[i].l,q[i].r),q[i].id=i;
int siz=sqrt(n+1);
For(i,1,n) bl[i]=(i-1)/siz+1; //分块
sort(q+1,q+m+1,cmp);
int l=1,r=0;
For(i,1,m){
while(l>q[i].l) Add(--l); //指针移动
while(r<q[i].r) Add(++r);
while(l<q[i].l) Del(l++);
while(r>q[i].r) Del(r--);
ans[q[i].id]=now; //离线答案别统计错了
}
For(i,1,m) printf("%d\n",ans[i]);
}
至此，我们大概可以总结出来莫队适用的问题：
-
问题可以离线。
-
问题的询问是以区间的形式给出。
-
插入或删除一个数的操作能以低复杂度快速实现。
补充：\(l,r\) 指针的移动顺序。
这里我建议大家莫队统一采用我上面给出的顺序来写，即 --l,++r,l++,r-- 的顺序来写，否则可能会因为奇怪的原因 RE。
具体的原因大家可以取 OI-Wiki 上看，有相对详细的介绍。
2 带修改的莫队
我们同样还是以例题的方式来引入：题目链接。
我们之前是引入了两个指针 \(l,r\)，现在我们考虑再引入一个指针 \(t\)，代表当前进行的修改操作。对于每个询问，我们记录它是在第几次操作之后（称其为“时间戳”），移动完 \(l,r\) 指针之后，我们再比较一下指针 \(t\) 和当前询问的时间戳关系：如果当前询问是在第 \(t\) 次修改之前的，那么就将多的几次修改改回去；如果当前询问是在第 \(t\) 次修改之后的，我们就要多进行几次修改。
排序方式：按照询问左端点所在块的编号排序，左端点所在块相同时按右端点所在块的编号排序，右端点所在块相同时按照时间戳排序。当块长取 \(n^{\frac{2}{3}}\) 时取得最优复杂度 \(O(n^\frac{5}{3})\)，具体证明过程不再展示。
直接说有点抽象，结合代码理解：
using Query=struct{int l,r,tim,id;};
using Modify=struct{int pos,col;};
int n,m,a[N];
int block,now,bl[N],cnt[N],ans[N];
int tot1,tot2;Query q[N];Modify c[N];
bool cmp(const Query &a,const Query &b){ //新的排序方式
if(bl[a.l]!=bl[b.l]) return bl[a.l]<bl[b.l];
if(bl[a.r]!=bl[b.r]) return bl[a.r]<bl[b.r];
return a.tim<b.tim;
}
namespace MoOrz{
void Add(int pos){
cnt[a[pos]]++;
if(cnt[a[pos]]==1) now++;
}
void Del(int pos){
cnt[a[pos]]--;
if(!cnt[a[pos]]) now--;
}
void Change(int pos,int i){
if(c[pos].pos>=q[i].l&&c[pos].pos<=q[i].r){ //要注意的一点，只有修改的位置在当前询问的区间内的时候才会对答案产生影响
if(--cnt[a[c[pos].pos]]==0) now--;
if(++cnt[c[pos].col]==1) now++;
}
swap(c[pos].col,a[c[pos].pos]); //这里是非常妙的一点，解释一下
//假如某次修改是把a[3]的颜色3改为7，那么下次再改回来的时候就相当于把a[3]的7再改回3
// 不难发现其实就是交换了一下，非常方便
}
void Solve(){
int l=1,r=0,t=0;
For(i,1,tot1){
while(l>q[i].l) Add(--l);
while(r<q[i].r) Add(++r);
while(l<q[i].l) Del(l++);
while(r>q[i].r) Del(r--);
// printf("q[i].l:%d q[i].r:%d now:%d t:%d q[i].tim:%d\n",q[i].l,q[i].r,now,t,q[i].tim);
while(t<q[i].tim) Change(++t,i);
while(t>q[i].tim) Change(t--,i);
ans[q[i].id]=now;
}
}
}
void Main(){
read(n,m);For(i,1,n) read(a[i]);
For(i,1,m){
char opt;cin>>opt;
if(opt=='Q') q[++tot1].l=read(),q[tot1].r=read(),q[tot1].tim=tot2,q[tot1].id=tot1;
else c[++tot2].pos=read(),c[tot2].col=read(); //修改要单独拎出来
}
block=pow(n,(db)2.0/3.0);For(i,1,n) bl[i]=(i-1)/block+1; //注意块长的大小
sort(q+1,q+tot1+1,cmp);MoOrz::Solve();
For(i,1,tot1) printf("%d\n",ans[i]);
}
3 树上莫队
3.1 子树统计相关
图太丑了呜呜呜……
这个其实大家应该都比较熟悉了，子树问题可以通过预处理 dfs 序和子树大小，来转换成区间问题，以 \(x\) 为根的子树所对应的区间就可以表示为 [dfn[x],dfn[x]+siz[x]-1]。
例题没找到合适的，有人有的话戳我一下。
3.2 路径统计相关
不难发现，路径问题是无法用普通 dfs 序来解决的。
但是，我们有一种新的序列——欧拉序，也叫括号序。
它的求法十分简单，让每个点入栈两次即可，先上一张图（图片来自网络，如果侵权立马删除）：
不妨观察下它有什么性质：以 \(3\) 为例，\(3\) 在欧拉序中一共出现了两次，且两个 \(3\) 中间出现的点有 \(6,8,9,10,11\)，不难发现它们其实都是 \(3\) 子树内的点，这种优美的性质就可以很好地帮我们解决树上莫队问题。
我们不妨记点 \(i\) 在欧拉序中第一个出现位置为 \(st[i]\)，第二个出现位置为 \(ed[i]\)，现在有两个点 \((u,v)\)，如何将它们路径上的点转化为对应区间呢？
我们分两种情况来考虑。
不妨设 \(st[u]<st[v]\)，第一种情况就是 \(lca(u,v)=u\)，即 \(u\) 是 \(v\) 的直接祖先，此时我们可以直接将欧拉序的区间 \([st[u],st[v]]\) 拉出来使用，并且将区间中出现过两次的点不加入答案的计算。根据性质，路径上的点一定都会只出现一次。
第二种情况即 \(u,v\) 分属不同的子树中，这个时候我们直接把区间 \([ed[u],st[v]]\) 拉出来使用，同样区间中出现过两次的点忽略不计，理由同上。当然这么做不难发现 \(lca(u,v)\) 也被忽略掉了，特判一下加上就可以了。
至于这么做的具体证明就不再给了，结合上面的图其实应该很好理解。
求欧拉序的代码放在这里：
void dfs1(int now,int fath){
fa[now]=fath;dep[now]=dep[fath]+1;siz[now]=1;
st[now]=++clk;pts[clk]=now;
for(int to:G[now]){
if(to==fath) continue;
dfs1(to,now);
siz[now]+=siz[to];
if(siz[to]>siz[son[now]]) son[now]=to;
}
ed[now]=++clk;pts[clk]=now;
}
例题：题目链接。
套用欧拉序其实就成了区间不同颜色数的问题，具体的实现及细节直接看我的代码吧。
void dfs1(int now,int fath){
fa[now]=fath;dep[now]=dep[fath]+1;siz[now]=1;
st[now]=++clk;pts[clk]=now;
for(int to:G[now]){
if(to==fath) continue;
dfs1(to,now);
siz[now]+=siz[to];
if(siz[to]>siz[son[now]]) son[now]=to;
}
ed[now]=++clk;pts[clk]=now;
}
void dfs2(int now,int lmt){
top[now]=lmt;
if(!son[now]) return;
dfs2(son[now],lmt);
for(int to:G[now]){
if(top[to]) continue;
dfs2(to,to);
}
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void Lisanhua(){
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;
For(i,1,n) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
}
void prework(){
For(i,1,m){
int x=read(),y=read(),lca=LCA(x,y);
if(st[x]>st[y]) swap(x,y);
if(lca==x) q[i].l=st[x],q[i].r=st[y];
else q[i].l=ed[x],q[i].r=st[y],q[i].lca=lca;
q[i].id=i;
}
}
void Add(int pos){
cnt[a[pos]]++;
if(cnt[a[pos]]==1) Ans++;
}
void Del(int pos){
cnt[a[pos]]--;
if(!cnt[a[pos]]) Ans--;
}
void Change(int pos){
used[pos]?Del(pos):Add(pos);
used[pos]^=1;
}
void Main(){
read(n,m);block=sqrt(n);
For(i,1,n) a[i]=b[i]=read();
For(i,1,n<<1) bl[i]=(i-1)/block+1;
Lisanhua();
For(i,1,n-1){
int u=read(),v=read();
G[u].pb(v);G[v].pb(u);
}
dfs1(1,0);dfs2(1,1);prework();
sort(q+1,q+m+1,cmp);
int l=1,r=0;
For(i,1,m){
while(l>q[i].l) Change(pts[--l]);
while(r<q[i].r) Change(pts[++r]);
while(l<q[i].l) Change(pts[l++]);
while(r>q[i].r) Change(pts[r--]);
if(q[i].lca) Change(q[i].lca);
ans[q[i].id]=Ans;
if(q[i].lca) Change(q[i].lca);
}
For(i,1,m) printf("%d\n",ans[i]);
}
4 回滚莫队
有的时候，我们可能发现，对于某些题目，添加操作十分好实现，但是删除操作却异常困难（或者反过来）。这个时候，我们可能就需要用到回滚莫队。
就比如这道题：题目链接。
我们发现，如果单纯只是加入一个数的话，题目要求的东西其实是非常好维护的。但是删除呢？次大值我们是不可能快速地直接维护的。
我们仍然从莫队排序后的性质出发，看看能不能找到解决问题的方法。既然我们实现不了删除，那么我们直接不删除不就行了吗？
同样还是对序列分好块，这次我们需要预处理出第 \(i\) 号块的左端点 \(L[i]\) 和第 \(i\) 号块的右端点 \(R[i]\)，对于每次询问，考虑如下情况：
-
如果这次询问的左右端点都在同一个块内的话，那么我们不妨直接暴力从前往后扫一遍，复杂度只有 \(O(\sqrt n)\)。
-
否则，如果当前询问的左端点和上一个询问左端点不在同一块内，我们直接将答案和贡献清零，并把 \(l\) 指针移动到当前块的右端点 \(+1\)，\(r\) 指针移动到当前块的右端点。
-
每次移动，先把 \(r\) 指针移动到对应位置，对于左端点同属一块的询问，右端点是单调向右的，因此 \(r\) 指针的贡献不需要消除；随后，把 \(l\) 指针移动到对应的端点，统计完答案后，将 \(l\) 指针归回到原位，因为 \(l\) 指针无法保持单调，对答案带来的贡献不一定能留下去。
时间复杂度分析：对于 \(r\) 指针，每个块最多移动 \(O(n)\) 次，总共 \(\sqrt n\) 个块，时间复杂度 \(O(n\sqrt n)\)；对于 \(l\) 指针，每次最多移动 \(O(\sqrt n)\) 次，总共有 \(n\) 次询问，复杂度 \(O(n\sqrt n)\)。
综上所述，回滚莫队的复杂度也只有 \(O(\sqrt n)\)，十分优秀。
具体实现的细节直接看代码。
using Query=struct{int l,r,id;};
int n,m,q,a[N],b[N],cnt1[N],cnt2[N];
int block,tot,bl[N],L[N],R[N];
int now_ans,ans[N];
Query qry[N];
bool cmp(const Query &a,const Query &b){return (bl[a.l]^bl[b.l])?bl[a.l]<bl[b.l]:a.r<b.r;}
void build(){ //建块过程
block=sqrt(n);
For(i,1,n){
bl[i]=(i-1)/block+1;
if(bl[i]!=bl[i-1]) L[bl[i]]=i,tot++;
R[bl[i]]=i; //记录每个块的左右端点
}
}
void Add(int v,int &now_ans){
cnt1[v]++;
now_ans=max(now_ans,cnt1[v]*b[v]);
}
void Del(int v){cnt1[v]--;}
void Main(){
read(n,q);
For(i,1,n) read(a[i]),b[++m]=a[i];
sort(b+1,b+m+1);m=unique(b+1,b+m+1)-b-1; //离散化一下
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
For(i,1,q) read(qry[i].l,qry[i].r),qry[i].id=i;
build();sort(qry+1,qry+q+1,cmp); //对询问排序
int l=1,r=0,last=0;
For(i,1,q){
if(bl[qry[i].l]==bl[qry[i].r]){ //如果左右端点在一个块内，直接暴力也是没问题的
For(j,qry[i].l,qry[i].r) cnt2[a[j]]++;
For(j,qry[i].l,qry[i].r) ans[qry[i].id]=max(ans[qry[i].id],cnt2[a[j]]*b[a[j]]);
For(j,qry[i].l,qry[i].r) cnt2[a[j]]--;
continue;
}
if(bl[qry[i].l]!=last){ //如果和左端点上次询问不在一个块，重置指针
while(r>R[bl[qry[i].l]]) Del(a[r--]);
while(l<=R[bl[qry[i].l]]) Del(a[l++]);
now_ans=0;last=bl[qry[i].l];
}
while(r<qry[i].r) Add(a[++r],now_ans); //右端点直接移动
int l2=l,tmp=now_ans; //答案要记一下，因为右端点的贡献可以延续下去，左端点不行
while(l2>qry[i].l) Add(a[--l2],tmp);
ans[qry[i].id]=tmp;
while(l2<l) Del(a[l2++]); //回滚回去
}
For(i,1,q) printf("%lld\n",ans[i]);
}