浅谈详解莫队算法

Aurelia_Veil · 2025-07-21 19:32:37 · 算法·理论

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。

源自 OI Wiki

一、普通莫队思想

本板块例题：洛谷 P3901 数列找不同，请查看题目后阅读，本版块不会添加“在这道题中” 的前缀！

1. 新型暴力

在做题中，特别是区间最值类问题，我们常常想到一种滑动区间的方法解决这类问题。比如例题。

定义相关变量或数组：

我们使用 a_i 记录输入的数列，l 和 r 记录我们现在的答案区间的左右端点，使用 al_i 和 ar_i 存储我们输入的答案区间的左右端点（基础变量或数组）。

我们还要用 t_i 记录 i 在这个区间中出现了几次，使用 noww 记录目前是否相同的有多少个（因此，noww \ge 1 为不符合题目条件，noww = 0 为符合题目条件）（题目所需变量或数组）。

操作：

在遇到 [al_i,ar_i] 的目标答案区间，我们要尝试将目前的答案区间移动到目标区间上，也就是重复执行将目前的区间左右端点每次向目标区间左右端点移动一格。

为什么是一格？因为我们还要统计答案（~~你光移动区间有什么用~~）我们分左右端点考虑。

左端点：

如果左端点要向左移动，说明需要增加 a_{l-1} 这个位置对答案的贡献，也就是 l \gets l-1 , t_l \gets t_l+1，如果 t_l 在更新后为 2，说明当次不满足条件，将 noww \gets noww+1。

反之，如果左端点要向右移动，说明需要减少 a_{l} 这个位置对答案的贡献，也就是 t_l \gets t_l-1 , l \gets l+1（注意先后顺序不同），如果 t_l 在更新后为 1，说明当次满足条件，将 noww \gets noww-1。

右端点：

右端点和左端点完全是反着来的。

如果右端点要向左移动，说明需要减少 a_{r} 这个位置对答案的贡献，也就是 t_r \gets t_r-1 , r \gets r-1，如果 t_r 在更新后为 1，说明当次满足条件，将 noww \gets noww-1。

反之，如果右端点要向右移动，说明需要增加 a_{r+1} 这个位置对答案的贡献，也就是 r \gets r+1 , t_r \gets t_r+1，如果 t_r 在更新后为 2，说明当次不满足条件，将 noww \gets noww+1。

时间复杂度：

我们当一次恶心的出题人来尝试卡一下，很容易，我们直接让 l 和 r 在 1 和 n 之间反复跳跃即可，最坏时间复杂度为 O(QN)，直接超时。

2. 优化暴力

思考：

我们想一想哪里还可以优化？对啦，将输入区间进行排序！

我们现在要想一想如何排序，相信有聪明的人已经知道了，那就是分块，我们可以将长度为 N 的数列分为 \sqrt{N} 的长度为 \sqrt{N} 的块（具体原因见后文时间复杂度），这样的话我们就可以以左端点所在块编号升序为第一关键字，以右端点位置升序为第二关键字排序。

为什么要做这样排序，你看接下来的时间复杂度就知道了。

对于四个端点移动的顺序：

我们要时刻考虑端点移动是否会出现 l>r+1 的情况，因为这种情况就会出现一些元素的统计是负数的情况，有可能会出现答案紊乱。

于是，我们就可以先扩大，再缩小，也就是 l--;r++;l++;r--（因此板块重复部分过多，故将移动操作简化），对于这个顺序，给出证明：

在 l-- 的过程中，因为 l 原本就小于等于 r+1，因此不会出现上述情况。
在 r++ 的过程中，因为 r 原本就大于等于 l-1，因此不会出现上述情况
在 l++ 的过程中，因为目标左右端点一定合法，且 r 已经扩大，不会出现 r 小于目标右端点的情况，因此不会出现上述情况。
在 r-- 的过程中，因为目标左右端点一定合法，且 l 已经扩大，不会出现 l 大于目标左端点的情况，因此不会出现上述情况。

3. 时间复杂度：

对于每一次在同一个块中的询问，我们的 l 至多只会移动 \sqrt{N} 次，而 r 至多只会移动 N 次，因此单次询问的时间复杂度为 O(\sqrt{N} + N)，总共为 O(\sqrt{N}(\sqrt{N}+N))，化简得 O(N\sqrt{N}+N)，N 可忽略不计，因此时间复杂度为 O(N\sqrt{N})。

4. 代码展示（用时 409ms）：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+101;
int n,m,le,cnt;
struct slt{
    int l,r,id;
}b[N];
int a[N],t[N]; 
int idd[N]; 
bool c[N];
bool cmp(slt a,slt b){//排序
    if(idd[a.l]!=idd[b.l]){
        return idd[a.l]<idd[b.l];
    }
    return a.r<b.r;
}
void add(int x){//新增元素
    if(t[a[x]]==1){
        cnt++;
    }
    t[a[x]]++;
}
void _add(int x){//减少元素
    t[a[x]]--;
    if(t[a[x]]==1){
        cnt--;
    } 
}
void _init(){
    for(int i=1;i<=n;i++){
        idd[i]=(i-1)/le+1;
    }
}
signed main(){
    scanf("%d%d",&n,&m);
    le=sqrt(n);
    _init();
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&b[i].l,&b[i].r);
        b[i].id=i;
    }
    sort(b+1,b+m+1,cmp);
    int topl=1,topr=0;
    for(int i=1;i<=m;i++){
        int nowl=b[i].l,nowr=b[i].r;
        while(topl>nowl){//移动端点
            topl--;
            add(topl);
        }
        while(topr<nowr){
            topr++;
            add(topr);
        }
        while(topl<nowl){
            _add(topl);
            topl++;
        }
        while(topr>nowr){
            _add(topr);
            topr--;
        }
        c[b[i].id]=cnt;
    }
    for(int i=1;i<=m;i++){
        if(c[i]==0){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

5. 适用范围

这道例题在左右端点移动是只用了 O(1) 的时间复杂度就更新了答案，那么如果为 O(K) 呢？

那么时间复杂度将变为 O(NK\sqrt{N}+NK)，时间复杂度大增，如果 K \ge \sqrt{N}，那么就不如暴力。因此，莫队尽量使用于更新答案为 O(1) 时间复杂度的题目。

二、带修莫队

本板块例题：洛谷 P1903 [国家集训队] 数颜色 / 维护队列，请查看题目后阅读。

1. 新增的操作

注意到这道题新增了一个操作：修改（变量为 K），但是现在的普通莫队只能支持静态查询，于是，便有了带修莫队。

2. 解决修改操作

注意到操作数是层层递进的，于是我们新增时间戳 tim，表示之前修改了多少次，于是我们就要多在时间这一维度上移动。

原来的移动顺序将变为 tim++;tim--;l--;r++;l++;r--。

3. 调整与优化

因为增加了一个维度，我们还要调整块长为 N^{\frac{3}{5}}（当然也可以简化成 N^{\frac{2}{3}}）（证明见后文）。

我们还需要修改排序关键字，以左端点所在块升序为第一关键字，以右端点所在块升序为第二关键字，以时间戳为第三关键字。

4. 排序原因

这里引用 OI-Wiki 的名言：

想一想，如果不把右端点分块：

乱序的右端点对于每个询问会移动 N 次。

有序的右端点会带来乱序的时间，每次询问会移动 K 次。

无论哪一种情况，带来的时间开销都无法接受。

~~别问为什么我不说，因为我也不好说，说了也差不多。~~

5. 时间复杂度与块长证明

我们设块长为 len，则有 \frac{N}{len} 个块。

记询问区间左端点处于第 i 个块并且询问区间右端点处于第 j 个块有多少个为 q_{i,j}

在每个处于同一个块中的一组询问，左端点每次至多移动 len 次，时间复杂度为 O(len)，时间单调递增为 O(K)。

使用公式表示为：

\begin{aligned} \sum_{i=1}^{\frac{N}{len}}\sum_{j=i+1}^{\frac{N}{len}}(q_{i,j} \cdot len + K) &=M \cdot len+ (\frac{N}{len})^2K\\ &= M \cdot len+\frac{N^2K}{len^2} \end{aligned}

为了使时间复杂度最小，考虑将此式设为极小值，即为 M \cdot len+\frac{N^2K}{len^2} = 0。

得出 len=\sqrt[3]{\frac{2N^2K}{M}}=\frac{\sqrt[3]{2}\sqrt[3]{N^2}\sqrt[3]{K}}{\sqrt[3]{M}}=\frac{2^{\frac{1}{3}}N^{\frac{2}{3}}K^{\frac{1}{3}}}{M^{\frac{1}{3}}}。

于是在块长取 \frac{2^{\frac{1}{3}}N^{\frac{2}{3}}K^{\frac{1}{3}}}{M^{\frac{1}{3}}}（忽略常数为 \frac{N^{\frac{2}{3}}K^{\frac{1}{3}}}{M^{\frac{1}{3}}}）的情况下，时间复杂度为 O(M^{\frac{2}{3}}N^{\frac{2}{3}}K^{\frac{1}{3}})。

在把 N、M 和 K 当作同量级下，时间复杂度会简化为我们常说的 O(N^{\frac{5}{3}})。

6. 展示代码（用时 7.24s）：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+101;
const int M=1e7+111;
int n,m,le,cnt;
struct slt{
    int l,r,t,id;
}b[N];
struct ins{
    int x,pre,now;
}tt[N];
int a[N],t[M]; 
int last[N];
bool vis[N];
int c[N];
int sid[N];
bool cmp(slt a,slt b){
    if(sid[a.l]!=sid[b.l]){//排序 
        return sid[a.l]<sid[b.l];
    }
    if(sid[a.r]!=sid[b.r]){
        return sid[a.r]<sid[b.r];
    }
    return a.t<b.t;
}
void add(int x){//增加或减少元素对答案的贡献 
    if(vis[x]==0){
        if(t[a[x]]==0){
            cnt++;
        }
        t[a[x]]++;
    }else{
        t[a[x]]--;
        if(t[a[x]]==0){
            cnt--;
        }
    }
    vis[x]=!vis[x];
}
void inst(int x,int pre,int now){//修改元素 
    if(vis[x]){
        add(x);
        a[x]=now;
        add(x);
    }else{
        a[x]=now;
    }
}
void _init(){//初始化 
    for(int i=1;i<=n;i++){
        sid[i]=(i-1)/le+1;
        last[i]=a[i];//last[i]指这个位置修改前的数值 
    }
}
signed main(){
    scanf("%d%d",&n,&m);
    le=pow(n,2.0/3);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    _init();
    int nowtt=0;
    int _nowtt=0;
    for(int i=1;i<=m;i++){
        char op;
        cin>>op;
        if(op=='Q'){
            _nowtt++;//增加询问时间戳 
            scanf("%d%d",&b[_nowtt].l,&b[_nowtt].r);
            b[_nowtt].t=nowtt;
            b[_nowtt].id=_nowtt;
        }else{
            int x,y;
            scanf("%d%d",&x,&y);
            nowtt++;//增加修改时间戳 
            tt[nowtt].x=x;
            tt[nowtt].pre=last[x];
            tt[nowtt].now=y;
            last[x]=y;
        }
    }
    sort(b+1,b+_nowtt+1,cmp);
    int topl=1,topr=0,topt=0;
    for(int i=1;i<=_nowtt;i++){
        int nowl=b[i].l,nowr=b[i].r;
        int nowt=b[i].t;
        while(topt<nowt){//移动时间维度 
            topt++;
            inst(tt[topt].x,tt[topt].pre,tt[topt].now);
        }
        while(topt>nowt){
            inst(tt[topt].x,tt[topt].now,tt[topt].pre);
            topt--;
        }
        while(topl<nowl){//移动区间 
            add(topl);
            topl++;
        }
        while(topl>nowl){
            topl--;
            add(topl);
        }
        while(topr<nowr){
            topr++;
            add(topr);
        }
        while(topr>nowr){
            add(topr);
            topr--;
        }
        c[b[i].id]=cnt;
    }
    for(int i=1;i<=_nowtt;i++){
        printf("%d\n",c[i]);
    }
    return 0;
}

三、回滚莫队（不删除莫队）

本板块例题：洛谷 P1903 【模板】回滚莫队 & 不删除莫队，请查看题目后阅读。

1. 新增的问题

这道题我们很容易就能 O(1) 算出在区域转移时新增的元素对答案的贡献，但是你想一想怎么删除 O(1) 算出贡献（也有写题是反过来的），那很难了，于是聪明的 OIER 们就想出了回滚莫队（不删除莫队）

2. 解决问题

顾名思义，回滚莫队就是回滚的，为了使区间转移时不删除或者不添加（本文章只讲解不删除的情况），我们需要尽量将左右区间向外扩大，具体步骤如下：

以左端点所属块（块长 \sqrt{n}）升序为第一关键字，右端点升序为第二关键字排序。
如果当前询问区间左端点所属块与上一次不同，就将当前答案区间右端点变为当前询问区间左端点所属块的右端点，将当前答案区间左端点变为当前询问区间左端点所属块的右端点位置加 1，并初始化所有有关存储答案的变量与数组。
如果当前询问区间的左右端点处于同一个块中，直接暴力求解。
否则：
- 如果询问区间的右端点大于当前答案区间的右端点，就不断将右端点扩展至询问区间的右端点。
- 存储当前答案以便快速撤回。
- 不断将当前答案区间的左端点扩展至询问区间的左端点。
- 存储当前答案。
- 使用上文存储变量立刻将答案撤回，并且将当前答案区间左端点向询问区间所在块的右端点位置加 1 移动（回滚）。

相信你看着过程知道了什么是回滚了。

其余细节基本不变。

3. 时间复杂度与块长

对于左右端点在同一块中暴力的情况，时间复杂度不超过 O(\sqrt{n})。

设块长为 len。

在其余情况下，对于每一个块，左端点最多移动 len 次，右端点最多移动 n 次，因此对于每一个询问的查询时间复杂度为 O(len+\sqrt{n})，总时间复杂度为 O(m\cdot len+\frac{n^2}{len})，取 len=\frac{n}{\sqrt{m}} 时最优（你可以自己算算），时间复杂度为 O(n\sqrt{m})。

4. 代码展示：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+101;
int n,m,le,ans;
struct slt{
    int l,r,id;
}b[N];
int sid[N];
int rsid[N];
int a[N],c[N],t[N]; 
int aa[N];
int lmin[N],rmax[N];
bool cmp(slt a,slt b){
    if(sid[a.l]!=sid[b.l]){
        return sid[a.l]<sid[b.l];
    }
    return a.r<b.r;
}
void addl(int x){
    if(rmax[a[x]]==0){
        rmax[a[x]]=x;
        return;
    }
    ans=max(ans,rmax[a[x]]-x);
}
void addr(int x){
    if(lmin[a[x]]==0){
        lmin[a[x]]=rmax[a[x]]=x;
        return;
    }
    rmax[a[x]]=x;
    ans=max(ans,rmax[a[x]]-lmin[a[x]]);
}
void _add(int x){
    if(rmax[a[x]]==x){
        rmax[a[x]]=0;
    }
}
void _init(){
    for(int i=1;i<=n;i++){
        sid[i]=(i-1)/le+1;
        rsid[sid[i]]=i;
    }
}
unordered_map<int,int>lip;
void lit(){//离散化
    sort(aa+1,aa+n+1);
    int coun=0;
    for(int i=1;i<=n;i++){
        if(i!=1&&aa[i]==aa[i-1]){
            continue;
        }
        coun++;
        lip[aa[i]]=coun;
    }
    for(int i=1;i<=n;i++){
        a[i]=lip[a[i]];
    }
}
int ll[N];
int pointt(int l,int r){//暴力求解
    int maxex=-1;
    for(int i=l;i<=r;i++){
        ll[a[i]]=0;
    }
    for(int i=l;i<=r;i++){
        if(ll[a[i]]==0){
            ll[a[i]]=i;
        }
        maxex=max(maxex,abs(i-ll[a[i]]));
    }
    for(int i=l;i<=r;i++){
        ll[a[i]]=0;
    }
    return maxex;
}
signed main(){
    scanf("%d",&n);
    le=sqrt(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        aa[i]=a[i];
    }
    lit();
    _init();
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&b[i].l,&b[i].r);
        b[i].id=i;
    }
    sort(b+1,b+m+1,cmp);
    int topl=1,topr=0;
    for(int i=1;i<=m;i++){
        int nowl=b[i].l,nowr=b[i].r;
        if(sid[nowl]!=sid[b[i-1].l]){//如果这个块与上一个不同
            fill(lmin,lmin+N,0);
            fill(rmax,rmax+N,0);
            topl=rsid[sid[topl]]+1;
            topr=topl-1;
            ans=0;
        }
        if(sid[nowl]==sid[nowr]){//如果左右端点处于同一个块
            c[b[i].id]=pointt(nowl,nowr);
        }else{
            while(topr<nowr){//移动区间
                topr++;
                addr(topr);
            }
            int tp_ans=ans;//存储答案以便快速撤回
            while(topl>nowl){
                topl--;
                addl(topl);
            }
            c[b[i].id]=ans;
            while(topl<=rsid[sid[nowl]]){
                _add(topl);
                topl++;
            }
            ans=tp_ans;
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",c[i]);
    }
    return 0;
}

感谢你的观看，能不能留下你的点赞收藏评论关注呢，谢谢！

~~下次一定！~~