浅谈莫队，带修莫队，高维莫队。树上莫队，莫队二次离线（暂无），回滚莫队及其应用 || 爆肝万余字 || 这里有 luogu 最全的莫队讲解！

· · 算法·理论

我不会滥用标题行了吧。

本专栏讲解了前人都没怎么讲解的莫队算法的拓展与进阶，对朴素莫队仍然有详细的讲解，并对时间复杂度和最优块长有了一个系统的整理与分析，是一个大集合。

一、普通莫队

莫队算法可以以 O(n\sqrt{q}) 解决一类离线区间询问问题，适用性极为广泛。

莫队算法的本质是在已知某区间的情况下，能逐步推出未知区间，我们以下面的 Simple Question I 作为例题。

:::info[Simple Question I] 维护一个长度为 n 的序列 A，要求多次询问不同区间里不同元素的个数。 :::

如果一个区间 [l,r] 我们维护好了，对于 r+1，我们显然可以 O(1) 去求出区间 [l,r] 内的与 A_{r+1} 相同的数的个数 f(l,r,r+1)。

如果 f(l,r,r+1)=0，说明 A_{r+1} 是第一次在 [l,r+1] 中出现，则 ans_{l,r+1}\to ans_{l,r}+1。

反之，说明 A_{r+1} 已经在 [l,r] 出现过了，则 ans_{l,r+1}\to ans_{l,r}。

如果要推出 [l,r-1]，我们可以计算 A_r 在区间 [l,r] 内的出现情况 f(l,r,r)。

如果 f(l,r,r)=1，说明区间内没有与 A_r 相同的数，ans_{l,r-1}\to ans_{l,r}-1。

反之，说明 A_r 多次出现，ans_{l,r-1}\to ans_{l,r}。

通过逐步递推，我们就可以推出所有的区间了。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],b[N],n,m,ans;
int lst=1,rst=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        while(l<lst){
            if(!b[a[lst-1]])ans++;
            b[a[lst-1]]++;
            lst--;
        }//递推[l,r]->[l-1,r]
        while(r>rst){
            if(!b[a[rst+1]])ans++;
            b[a[rst+1]]++;
            rst++;
        }//递推[l,r]->[l,r+1]
        while(l>lst){
            if(b[a[lst]]==1)ans--;
            b[a[lst]]--;
            lst++;
        }//递推[l,r]->[l+1,r]
        while(r<rst){
            if(b[a[rst]]==1)ans--;
            b[a[rst]]--;
            rst--;
        }//递推[l,r]->[l,r-1]
        cout<<ans<<'\n';
    }
}

时间复杂度 O(nm)，在所有区间均极大时有着较为优秀的时间复杂度，但对于如下 hack 数据，和暴力有着差不多的复杂度。

:::info[hack]

1 n
n/2 n/2
2 n-1
n/2-1 n/2+1
3 n-2
n/2-2 n/2+2
...

此时我们的递推就会出现来回跑的情况。 :::

二、排序优化

由于我们傻乎乎的挨个操作跑特别笨，由于每个操作不会有后效性，所以我们可以不按题目给的顺序进行递推。

此时我们的问题相当于：网格图上有 n 个点 (x_1,y_1),(x_2,y_2),...,(x_n,y_n)，构造一个排列 p，使得 p_1=1，求 \sum\limits_{2\le i \le n}|x_i-x_{i-1}|+|y_i-y_{i-1}| 的最小值。

首先，这是一个 NP-hard 问题，我们无法求出严格最短的路径，只需要设计一个较为优秀的方案即可。

一个明显的贪心策略是，我们以 l 为第一键值，r 为第二键值从小到大排序，但我们可以给出 hack：

:::info[hack]

1 1
1 n
2 2
2 n
...

此时虽然 l 的移动变成了 O(n) 的，但是 r 每次仍然需要来回跑，复杂度仍然是 O(nm)。 :::

这个策略其实有很多值得借鉴的地方，因为在 l 一定的情况下，r 的移动是 O(n) 的，但是此时的劣势在于 l 不同的情况有很多。

所以我们想到，把很多个 l 分到一个组里，组内顺序是可以改变的，这样的话对于每一个组内，r 的移动是 O(n) 的，此时决定移动范围的是组内的跑动以及不同组的跨越。

我们来分析组内的元素个数 x 对移动步数的影响：

总的移动次数为 O(qx+n+\frac{n^2}{x})，均值不等式一下得到 qx+n+\frac{n^2}{x}\ge n+2\sqrt{qx\times \frac{n^2}{x}}\ge n\sqrt{q}，在 x=\frac{n}{\sqrt{q}} 时取到最优。

下面给出 Simple Question I 的正确莫队代码 [^{1}]()：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int a[N], cnt[N], ans, block;
int n, m;
struct Query {
    int l, r, id;
} q[N];
int res[N]; 
bool cmp(const Query &x, const Query &y) {
    if (x.l / block != y.l / block) return x.l / block < y.l / block;
    return x.r < y.r;
}
void add(int pos) {
    cnt[a[pos]]++;
    if (cnt[a[pos]] == 1) ans++;
}
void remove(int pos) {
    cnt[a[pos]]--;
    if (cnt[a[pos]] == 0) ans--;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    block = n / sqrt(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 curL = 1, curR = 0;
    ans = 0;
    for (int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r;
        while (curL > l) add(--curL);
        while (curR < r) add(++curR);
        while (curL < l) remove(curL++);
        while (curR > r) remove(curR--);
        res[q[i].id] = ans;
    }
    for (int i = 1; i <= m; i++) {
        cout << res[i] << '\n';
    }

    return 0;
}

总结：莫队的操作其实和线段树的合并类似，但它没有多次合并的过程，且是单点合并，所以可以处理一些线段树无法区间合并的问题，但是在有修改时，莫队明显劣于线段树，操作空间受限。

三、基础莫队例题

ABC448F

这是我们提到的莫队的定义式，直接使用莫队排序即可通过。

P2709

此题与 Simple Question I 类似，但改为了求次数的平方。

很简单的推式子，我们只需要考虑 [l,r] 移动到 [l,r+1] 时的变化，假设第 r+1 个数在 [l,r] 中出现的次数为 x，则相当于从 x\to x+1，变化为 (x+1)^2-x^2=2x+1。

从 [l,r] 变到 [l,r-1]，假设第 r 个数在 [l,r-1] 中出现的次数为 x，则变化为 x^2-(x-1)^2=2x-1。

P4137

莫队和 bitset 的巧妙结合。

我们发现区间 [l,r] 的 mex 相当于在值域范围内第一个为 0 的，而 bitset 能够完全胜任这一点。

bitset 中的函数 _Find_first() 可以返回第一个 1 的下标，例如：

由于返回的是第一个 1，所以我们要将未出现的记为 1。

区间内的数为 0 2 1 4，则 bitset 内存的东西为 0010，_Find_first 的值为 3，所以区间 mex 的值为 3。

P4462

区间 [l,r] 的异或和相当于 r 的前缀异或和异或上 l-1 的前缀异或和。

此时 x 的贡献有两处，第一个是将 x 的前缀异或和 sum_x 出现次数加一，然后是加上前缀异或和为 sum_x \oplus k 的次数。

P5268

本题是莫队问题的变种。

注意到 f(l_1,r_1,x)=f(1,r_1,x)-f(1,l_1-1,x)，所以有：

f(l_1,r_1,x)\times f(l_2,r_2,x)=f(1,r_1,x)f(1,r_2,x)-f(1,r_1,x)f(1,l_2,x)-f(1,l_1,x)f(1,r_2,x)+f(1,l_1,x)f(1,l_2,x)

将 1 个询问拆成 4 个询问。

我们的莫队维护的就是两个端点 l',r'，计算的是 [1,l'] 和 [1,r']，维护方式与 Simple Problem I 类似。

P11659

由于需要满足 x<y<z，所以我们需要分别存储 a_x:a_y=4x:2x 的答案 f_{1,x}，a_x:a_y=2x:3x 的答案 f_{2,x} 和总共的答案 ans。

对于范围扩大，我们按开头的元素的新增来增加答案：

对于缩小，我们按结尾的元素的消失进行减小答案。

四、奇偶排序

我们在排序的时候会发现一个问题，在每次跨越块的时候右端点都会回到起点重新跑，于是我们可以优化一下，在每次到终点后从终点跑回起点，这样就减小了 2 倍的常数。 写成代码就是奇数块从小往大排，偶数块从大往小排。

bool cmp(node a, node b) {
        return block[a.l]^block[b.l] ? a.l<b.l : (block[a.l]&1 ? a.r<b.r : a.r>b.r);
}//奇数块内右边界升序，偶数块内右边界降序

五、带修莫队

温馨提示：带修莫队只用于单点修改，对于区间修改的情况，需要用前缀和，差分等维护。

我们可以增加一维操作时间维度，在操作区间符合后，我们可以暴力维护操作，对于每一个操作都直接进行修改，共有 3 个维度。

我们在排序的时候需要先按左端点的块的编号排序，再按右端点的块的编号排序，最后再按时间排序。

我们以 P1903 为例，展示代码 [^2]()。

inline void upd(int x, int t)//upd是对于时间上的变化所造成变化的维护
{
    if (qq[x].l <= qr[t].l && qr[t].l <= qq[x].r)del(a[qr[t].l]),add(qr[t].r); //如果这个修改的值在[l,r]区间内，则其变化将对答案造成影响
    swap(a[qr[t].l], qr[t].r);//因为修改后的下一次操作一定相反(即修改该位置->还原该位置->修改该位置...如此循环)，所以只需交换即可，而不需要写两个函数
}

bool cmp (const ques &a, const ques &b)
{
    return a.l / sz == b.l / sz ? a.r / sz == b.r / sz ? a.t < b.t : a.r < b.r : a.l < b.l;
}

int main()
{
    cin >> n >> m; sz = pow(n, 0.666);//设置块的大小
    for (int i = 1; i <= m; i++)
    {
        char op[5];
        int l, r;
        scanf("%s%d%d", op, &l, &r);
        if (op[0] == 'Q') qq[++cntq].id = {cntq,l,r,cntr};//时间轴是对只关于操作，所以可以类似一种离散化的方法，直接将时间改为上一次修改的时间
        else qr[++cntr].l = l, qr[cntr].r = r;
    }
    sort(qq + 1, qq + cntq + 1, cmp);
    while (lcur > qq[i].l) add(a[--lcur]);
    while (lcur < qq[i].l) del(a[lcur++]);
    while (rcur > qq[i].r) del(a[rcur--]);
    while (rcur < qq[i].r) add(a[++rcur]);
    while (tcur < qq[i].t) upd(i, ++tcur);
    while (tcur > qq[i].t) upd(i, tcur--);

复杂度分析：假设 x 为块长。

一个简略的证明是，对于每一个询问的端点移动复杂度为 O(x)，时间单调，复杂度为 O(t)。

总复杂度为 qx+(\frac{n}{x})^2t，在 x 取 \frac{n^{\frac{2}{3}}t^\frac{1}{3}}{q^\frac{1}{3}} 最小，为 q^\frac{2}{3}n^\frac{2}{3}t^\frac{1}{3}，复杂度大约为 n^\frac{5}{3}。

六、带修莫队例题：CF940F Machine Learning

可以说是 P4137 和带修莫队的结合，将 bitset 的操作照搬过来即可，这里不再赘述。

七、高维莫队

高维莫队通常是 3 维的，\ge 4 维很少见，如带修莫队就是高维莫队的典型应用，k 维莫队的时间复杂度大约为 n^{2-\frac{1}{k}}，块长大约取 n^\frac{k-1}{k} 最优。

注意在排序时是将前 k-1 维按块编号排序，最后一维从小到大排序。

小提示：交换两个维度的顺序在一些时候可以有效改善代码复杂度。

在修改时，按先将所有维度扩大，再将所有维度缩小的写法去写，不会有问题。

下面给出例题：

八、高维莫队例题

P5268

本题也可以不用容斥转正常 2 维莫队，直接使用 4 维莫队，复杂度大约为 n^\frac{7}{4}。

在 [l_1,r_1,l_2,r_2] 转移到 [l_1-1,r_1,l_2,r_2] 时将答案加上 f(l_1-1,l_2,r_2)，其余同理。

九、树上莫队

在处理树上路径的问题中，莫队是不能直接在树上求解的，对此，我们可以使用欧拉序的方式，将树上路径问题转为序列问题。

欧拉序是从根结点出发，按深度遍历整棵树，在每个点第一次被遍历到时记录，在第二次被遍历到时再次记录，例如：

它的欧拉序为 1 2 2 3 5 5 6 6 7 7 3 4 8 8 4 1。

欧拉序有一个重要的性质，可以帮助我们将树上问题转为序列问题（我们将 f_x 定义为 x 第一次在欧拉序中出现的位置，s_x 为第二次）：

例如：树上 1,5 的路径，等于欧拉序中 1 2 2 3 5，再减去 2 号点（出现两次）剩下的就是 1 3 5，为树上 1,5 间的点。

再比如：树上 7,8 的路径，等于欧拉序中 7 3 4 8，再加上最近公共祖先 1，为 7 3 4 8 1，也是树上 7,8 的路径。

有了欧拉序，我们就可以将树上问题转为序列问题了。

下面以 SP10707 举例，给出代码。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#define N 200000
using namespace std;
struct node
{
    int l,r,ll,rr,id,lca;
}q[N+5];
int n,m,a[N+5],st[N+5],ed[N+5],dfn[N+5],f[N+5],num,size[N+5],his[N+5],dep[N+5],son[N+5],top[N+5],c[N+5],tmp,blo,l=1,r,use[N+5],ans[N+5],data[N+5];
vector <int> d[N+5];
void dfs1(int u,int fa)  //树剖第一次深搜
{
    f[u]=fa;st[u]=++num;
    size[u]=1;his[num]=u;
    dep[u]=dep[fa]+1;
    vector <int>::iterator it;
    for (it=d[u].begin();it!=d[u].end();it++)
    {
        int v=(*it);
        if (v==fa)continue;
        dfs1(v,u);
        size[u]+=size[v];
        if (size[v]>size[son[u]])son[u]=v;
    }
    ed[u]=++num;his[num]=u;
}
void dfs2(int u,int to)   //树剖第二次深搜
{
    top[u]=to;
    if (son[u])dfs2(son[u],to);
    vector <int>::iterator it;
    for (it=d[u].begin();it!=d[u].end();it++)
    {
        int v=(*it);
        if (v!=son[u]&&v!=f[u])dfs2(v,v);
    }
}
int Lca(int x,int y)   //树剖求lca
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]])swap(x,y);
        x=f[top[x]];
    }
    if (dep[x]>dep[y])swap(x,y);
    return x;
}
void add(int x)
{
    tmp+=(++c[a[x]]==1);
}
void del(int x)
{
    tmp-=(--c[a[x]]==0);
}
void calc(int x)     //对点进行加入或删除
{
    (!use[x])?add(x):del(x);
    use[x]^=1;
}
int cmp(node x,node y)   //排序
{
    return (x.ll==y.ll)?(x.ll%2==1?x.r<y.r:x.r>y.r):x.l<y.l;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]),data[i]=a[i];
    sort(data+1,data+n+1);
    for(int i=1;i<=n;i++)a[i]=lower_bound(data+1,data+n+1,a[i])-data;  //离散化
    int x,y;
    for (int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        d[x].push_back(y);
        d[y].push_back(x);
    }
    dfs1(1,0); 
    dfs2(1,1);
    blo=n*2/sqrt(m*2/3);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        if (st[x]>st[y])swap(x,y);  //保证stx<sty
        q[i].id=i;
        q[i].lca=Lca(x,y);  
        if (q[i].lca==x)    //x,y在以x为根的子树中
        {
            q[i].l=st[x];
            q[i].r=st[y];
            q[i].ll=st[x]/blo;
            q[i].rr=st[y]/blo;
            q[i].lca=0;
        }
        else
        {
            q[i].l=ed[x];
            q[i].r=st[y];
            q[i].ll=ed[x]/blo;
            q[i].rr=st[y]/blo;
        }
    }
    sort(q+1,q+m+1,cmp);
    for (int i=1;i<=m;i++)
    {
        while (l>q[i].l)calc(his[--l]);
        while (r<q[i].r)calc(his[++r]);
        while (l<q[i].l)calc(his[l++]);
        while (r>q[i].r)calc(his[r--]);
        if (q[i].lca)calc(q[i].lca);//单独计算 LCA
        ans[q[i].id]=tmp;
        if (q[i].lca)calc(q[i].lca);//将 LCA 删去，避免多算
    }
    for (int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

十、莫队二次离线

太难了，先咕咕咕，预计 2026 年能写完，先别急。

十一、回滚莫队 / 不删除莫队

在一些较难处理区间缩小操作，但区间扩大好做的情况下，就可以使用回滚莫队。

:::warning 回滚莫队无法使用奇偶排序！！！ :::

每一个块 [bl,br] 内的答案，我们单独处理，以下均为每一个块内的操作。

首先将所有左右端点在同一个块内的查询全部暴力搜掉，接着我们初始化左右端点为 [br+1,br]，就可以保证询问的右区间是单调递增且不会回退了（因为所有 <br 都处理了）然后我们考虑处理左区间 l 的变化。

对于每一次要缩小左端点的情况，我们不妨暴力一点，将左端点**直接回退到初始 br+1 的位置，并重置所有的维护信息（可以用栈实现，记录当时的答案）。

:::warning 由于我们要记录 [br+1,r] 的答案，所以一定要后对 r 进行修改，先进行回溯！ :::

然后就做完了，时间复杂度为 O(n\sqrt{n}+n\sqrt{q})。