莫队算法入门

Collapsarr · 2025-05-12 22:16:15 · Algo. & Theory

莫队入门

前言

为了帮助某校学生更好地理解和自学莫队，故以本人学莫队的经历来写这篇文章，挽救这些学生。

一、普通莫队

我们用一道例题来引入：

给定一个长度为 n 的序列和 m 次询问，对于每一个询问区间 [l,r]，求出在这个区间内有多少个不同的数。

首先，我们考虑暴力做法，对于每一个区间，从 l 到 r 扫一遍，再用一个数组来维护某一个数是否出现过，这样做，我们的时间复杂度为 O(nm)，显然过不去。

然后，我们考虑优化，每次从上一个询问转移过来，利用上一次的答案来更新到这一次的答案，虽然这样做的时间复杂度依然为 O(nm)，只要让询问从最左边到最右边不断移动就好。

我们再次考虑优化，发现上一个做法的劣势之处在于 l,r 两个指针一直在左右乱跳，所以我们考虑离线操作，将所有的询问以 l 所在的位置为第一关键字，r 所在的位置为第二关键字进行排序，再让 l,r 两个指针左右移动，这样，我们的复杂度就变成了 O(n^2+m)。

此时，我们离莫队算法已经不远了，而莫队算法的精髓就在于此，我们又双叒叕地发现上面的操作劣在了 r 指针移动太频繁了，所以考虑将这种移动均匀分配给 l,r 两个指针，将原序列分成 \frac{n}{B} 个块长为 B 的块，排序时以 l 所在的位置的块为第一关键字，r 所在的位置的块为第二关键字进行排序，这样我们就可以在 O(n\sqrt{m}) 的时间复杂度内将所有询问处理完。

关于这里的复杂度的证明如下：

已知块长为 B，对于左端点在同一个块里面的询问，右端点至多从 1 移动到 n，也就是 O(n)，而左端点最多移动 \frac{n}{B} 个块，但是移动时可能会跨块，所以还会有 O(mB) 的时间复杂度，所以最终的时间复杂度即为 O(\frac{n^2}{B}+mB)，对其使用均值不等式得 B=\frac{n}{\sqrt{m}} 时复杂度最优为 O(n\sqrt{m})。

我们现在就可以普遍化这个想法，即假设我们现在有问题区间 [l,r] 的答案 ans，并且我们有一种操作可以使得我们在 O(1) 的时间复杂度内将答案扩展到与区间 [l,r] 相邻的区间（分别是 [l+1,r],[l-1,r],[l,r+1],[l,r-1]），那我们就可以在 O(n\sqrt{m}) 的时间复杂度内求出所有问题的答案，这就是普通的莫队算法。

洛谷上的普通莫队例题 P1972，虽然在洛谷加强数据后过不了了，但还是可以当做入门题练练手的：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'||'9'<ch)
    {
        if(ch=='-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int inf = 1e18,N = 1e6 + 10;

int n,m,a[N],B,sum[N],ans[N],anss;

struct que
{
    int l,r,ll,rr,id;
}q[N];

bool operator<(que x,que y)
{
    //奇偶化排序
    return (x.ll==y.ll)?((x.r==y.r)?(0):((x.ll&1)^(x.r<y.r))):(x.l<y.l);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    n = read();
    for(int i = 1;i<=n;i++)
    {
        a[i] = read();
    }
    m = read();
    B = n / sqrt(m);
    for(int i = 1;i<=m;i++)
    {
        q[i].l = read(),q[i].r = read(),q[i].id = i;
        //对询问进行分块
        q[i].ll = (q[i].l-1) / B + 1,q[i].rr = (q[i].r-1) / B + 1;
    }
    //排序询问
    sort(q+1,q+1+m);
    int l = q[1].l,r = q[1].l - 1;
    for(int i = 1;i<=m;i++)
    {
        //转移区间
        while(l>q[i].l)
        {
            anss += (++sum[a[--l]]==1);
        }
        while(r<q[i].r)
        {
            anss += (++sum[a[++r]]==1);
        }
        while(l<q[i].l)
        {
            anss -= (--sum[a[l++]]==0);
        }
        while(r>q[i].r)
        {
            anss -= (--sum[a[r--]]==0);
        }
        //记录询问的答案
        ans[q[i].id] = anss;
    }
    for(int i = 1;i<=m;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

优化

关于普通莫队的优化是奇偶化排序，我们让在奇数块的查询的右端点从左到右排序，而在偶数块的查询的右端点从右到左进行排序，这样我们就可以让在奇数块查询完的右端点再返回到左端点，优化了右端点的移动次数，实现方法同上个代码的排序函数。

二、带修莫队

莫队算法本身并不能进行修改，不过我们可以让它像 dp 一样加上时间维度，每次 l,r 端点移动完后再移动时间维度，就可以完成修改操作了，只不过我们要将排序操作修修改改，具体的时间复杂度的分析见 OI WiKi。

对于时间维度可以参考下面这个图来理解：

对应洛谷上的例题为 P1903，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define intt __int128

int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'||'9'<ch)
    {
        if(ch=='-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int inf = 1e18,N = 1e6 + 10;

int n,m,a[N],B,id[N],tot,ans[N],sum[N],anss;
pair<int,int> u[N];

struct que
{
    int l,r,id,t;
}q[N];

bool operator<(que x,que y)
{
    //三个关键字的排序
    return (id[x.l]==id[y.l])?((id[x.r]==id[y.r])?(x.t<y.t):(x.r<y.r)):(x.l<y.l);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    B = pow(n,2.0/3);
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
        id[i] = (i-1) / B + 1;
    }
    char s;
    for(int i = 1,l,r,time = 0;i<=m;i++)
    {
        cin>>s>>l>>r;
        if(s=='Q')
        {
            //记录询问的左右端点，编号，时间戳
            q[++tot] = {l,r,tot,time};
        }
        else
        {
            //维护修改的时间戳
            u[++time] = {l,r};
        }
    }
    sort(q+1,q+1+tot);
    int l = q[1].l,r = q[1].l - 1,t = 0;
    for(int i = 1;i<=tot;i++)
    {
        //扩展区间
        while(l>q[i].l)
        {
            --l;
            anss += (sum[a[l]]==0);
            ++sum[a[l]];
        }
        while(r<q[i].r)
        {
            ++r;
            anss += (sum[a[r]]==0);
            ++sum[a[r]];
        }
        while(l<q[i].l)
        {
            --sum[a[l]];
            anss -= (sum[a[l]]==0);
            ++l;
        }
        while(r>q[i].r)
        {
            --sum[a[r]];
            anss -= (sum[a[r]]==0);
            --r;
        }
        //扩展时间
        while(t<q[i].t)
        {
            ++t;
            if(l<=u[t].first&&u[t].first<=r)
            {
                sum[a[u[t].first]]--;
                anss -= (sum[a[u[t].first]]==0);
                anss += (sum[u[t].second]==0);
                ++sum[u[t].second];
                //此时要交换，不能直接赋值
                //因为之后可能会回退此次修改操作
                swap(a[u[t].first],u[t].second);
            }
            else
            {
                swap(a[u[t].first],u[t].second);
            }
        }
        while(t>q[i].t)
        {
            if(l<=u[t].first&&u[t].first<=r)
            {
                sum[a[u[t].first]]--;
                anss -= (sum[a[u[t].first]]==0);
                anss += (sum[u[t].second]==0);
                ++sum[u[t].second];
                //此时要交换，不能直接赋值
                //因为之后可能会增加此次修改操作
                swap(a[u[t].first],u[t].second);
            }
            else
            {
                swap(a[u[t].first],u[t].second);
            }
            t--;
        }
        //记录答案
        ans[q[i].id] = anss;
    }
    for(int i = 1;i<=tot;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

三、回滚莫队

对于一些需要莫队算法的题，但是这些题的增加或者删除操作的某一个不是那么好实现，这时候，回滚莫队就应运而生了，具体而言，回滚操作就是回退到某一个历史版本，利用这个操作来规避带增加或者删除操作。

以洛谷中 AT_joisc2014_c 歴史の研究来举具体的例子：

在这道题中，增加操作很好实现，我们可以直接用桶维护每一个数出现的次数然后乘上自己的值，而删除操作就不好实现了，如果我们改变了最大值，我们还有次大值、次次大值、次次次大值······这样就不好维护了，于是我们用回滚操作来替代删除操作，具体步骤如下：

像普通莫队一样进行排序，不过不能使用奇偶化排序，要严格按照左端点所在块为第一关键字，右端点的位置升序为第二关键字。
最开始处理的时候 l 端点为第一个块的右端点加一，r 端点为第一个块的右端点
按照排序进行处理
- 如果左右两个端点在同一个块内，那么直接暴力进行处理。
- 对于不在同一个块内的询问，我们让右端点向右进行扩展，扩展结束后，我们记录此时的答案及对应的状态，然后向左扩展左端点，扩展结束后，记录现在的答案，然后将左端点和数组回退到记录下的状态。
- 如果某一个询问的左端点超过了 l 的值，那么让 l,r 两个端点先回到对应块的右端点位置，在进行操作。

具体的操作可以参照代码来理解：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define intt __int128

int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'||'9'<ch)
    {
        if(ch=='-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int inf = 1e18,N = 1e5 + 10;

int n,m,a[N],b[N],B,id[N],tot,L[N],R[N],cnt,ans[N],anss;
int sum[N],__sum[N];

struct que
{
    int l,r,id;
}q[N];

bool operator<(que x,que y)
{
    return (id[x.l]==id[y.l])?(x.r<y.r):(x.l<y.l);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    n = read(),m = read();
    B = n / sqrt(m);
    for(int i = 1;i<=n;i++)
    {
        a[i] = b[i] = read();
        id[i] = (i-1) / B + 1;
    }
    cnt = id[n];
    sort(b+1,b+1+n);
    tot = unique(b+1,b+1+n) - b - 1;
    for(int i = 1;i<=n;i++)
    {
        //离散化
        a[i] = lower_bound(b+1,b+1+tot,a[i]) - b;
    }
    for(int i = 1;i<=cnt;i++)
    {
        L[i] = R[i-1] + 1;
        R[i] = R[i-1] + B;
    }
    R[cnt] = n;
    for(int i = 1;i<=m;i++)
    {
        q[i] = {read(),read(),i};
    }
    sort(q+1,q+1+m);
    for(int i = 1,l = 1,r = 0,lb = 0,tmp,dl;i<=m;i++)
    {
        if(id[q[i].l]==id[q[i].r])
        {
            //暴力处理询问
            for(int j = q[i].l;j<=q[i].r;j++)
            {
                __sum[a[j]]++;
            }
            for(int j = q[i].l;j<=q[i].r;j++)
            {
                ans[q[i].id] = max(ans[q[i].id],b[a[j]]*__sum[a[j]]);
            }
            for(int j = q[i].l;j<=q[i].r;j++)
            {
                --__sum[a[j]];
            }
        }
        else
        {
            if(id[q[i].l]!=lb)
            {
                //将左右端点回到块的右端点对应位置
                while(r>R[id[q[i].l]])
                {
                    --sum[a[r--]];
                }
                while(l<R[id[q[i].l]]+1)
                {
                    --sum[a[l++]];
                }
                anss = 0;
                lb = id[q[i].l];
            }
            //扩展右端点
            while(r<q[i].r)
            {
                ++sum[a[++r]];
                anss = max(anss,sum[a[r]]*b[a[r]]);
            }
            //记录当时的情况
            dl = l,tmp = anss;
            //扩展左端点
            while(dl>q[i].l)
            {
                ++sum[a[--dl]];
                anss = max(anss,sum[a[dl]]*b[a[dl]]);
            }
            //记录答案并回退操作
            ans[q[i].id] = anss;
            anss = tmp;
            while(dl<l)
            {
                --sum[a[dl++]];
            }
        }
    }
    for(int i = 1;i<=m;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

四、树上莫队

请先保证您已经学过了树链剖分以及 LCA 的相关知识。

树上莫队需要先把这棵树压成一个序列，然后在这个序列上跑莫队。

具体的依然用题来举例子：

洛谷中的 SP10707 COT2 - Count on a tree II：

这道题让我们求出两个点间路径上的点的不同颜色的个数，我们先对整棵树跑树链剖分，并跑出来这棵树的欧拉序，然后将询问转换到这个欧拉序上，具体会有两种情况，参考图片理解：

这棵树的欧拉序为 (1,2,2,4,5,5,3,6,6,3,4,1)

设 x 和 y 分别为两个查询的节点，定义 dep_i 为 i 号节点的深度，dfn_i 为欧拉序中第 i 个节点，st_i 为 i 号节点在欧拉序中的起始位置，ed_i 为 i 号节点在欧拉序中的结束位置，lca_{i,j} 为 i,j 两个节点的最近公共祖先。

如果 st_x\gt st_y，那么先交换 x,y 两个节点。
交换完成后，如果 lca_{x,y}=x，那么将对应询问改为 st_x,st_y，例如 x=4,y=6 此时对应的欧拉序区间为 (4,5,5,3,6)，其中的 5 号节点因为进出了各一次，不计入答案，4,6 两个节点在这条链上，直接统计掉。
否则将询问改为 ed_x,st_y，例如 x=2,y=5 此时对应的欧拉序区间为 (2,4,5)，取 ed_x 可以保证 x 节点被记入答案，取 st_y 则可以保证 y 节点只进入一次，保证被计入答案，但此时会有一个问题，我们会发现 lca_{x,y} 也就是 1 号节点没有被计入答案，那我们就在最后处理的时候额外加上它们的 lca_{x,y} 就可以了。

具体的求 lca_{x,y} 我们可以用树剖来求，排序无所谓，进不进行奇偶化都可以。

具体实现看代码：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)

int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'||'9'<ch)
    {
        if(ch=='-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int inf = 1e18,N = 1e6 + 10;

vector<int> d[N];
int n,m,a[N],b[N];
int head[N],siz[N],son[N],fa[N],dep[N],top[N],dfn[N],st[N],ed[N],tot,rt,cnt;
int B,id[N],anss,ans[N],sum[N];
bool falg[N];

struct que
{
    int l,r,ll,rr,id,lca;
    bool operator<(const que x) const
    {
        //奇偶化排序
        return (ll==x.ll)?((r==x.r)?(0):(((ll&1)^(r<x.r)))):(l<x.l);
    }
}q[N];

inline void dfs1(int u,int f)
{
    dfn[++cnt] = u,st[u] = cnt,
    siz[u] = 1;
    for(vector<int>::iterator it = d[u].begin();it!=d[u].end();it++)
    {
        int v = (*it);
        if(v!=f)
        {
            fa[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v,u);
            siz[u] = siz[v];
            if(siz[v]>siz[son[u]])
            {
                son[u] = v;
            }
        }
    }
    //求欧拉序
    dfn[++cnt] = u,ed[u] = cnt;
}

inline void dfs2(int u,int tp)
{
    top[u] = tp;
    if(son[u])
    {
        dfs2(son[u],tp);
    }
    for(vector<int>::iterator it = d[u].begin();it!=d[u].end();it++)
    {
        int v = (*it);
        if(v!=son[u]&&v!=fa[u])
        {
            dfs2(v,v);
        }
    }
}

inline int lca(int x,int y)
{
    //树剖lca
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        {
            swap(x,y);
        }
        x = fa[top[x]];
    }
    if(dep[x]>dep[y])
    {
        swap(x,y);
    }
    return x;
}

inline void cala(int x)
{
    (falg[x])?(anss-=(--sum[a[x]]==0)):(anss+=(++sum[a[x]]==1));
    falg[x] ^= 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    n = read(),m = read();
    for(int i = 1;i<=n;i++)
    {
        a[i] = read();
        b[i] = a[i];
    }
    sort(b+1,b+1+n);
    int cb = unique(b+1,b+1+n) - b - 1;
    for(int i = 1;i<=n;i++)
    {
        //离散化
        a[i] = lower_bound(b+1,b+1+cb,a[i]) - b;
    }
    for(int i = 1,u,v;i<n;i++)
    {
        u = read(),v = read();
        d[u].push_back(v);
        d[v].push_back(u);
    }
    rt = 1;
    fa[1] = 1,dep[1] = 1;
    //树链剖分
    dfs1(1,0);
    dfs2(1,1);
    B = n*2/sqrt(m*2/3);
    for(int i = 1;i<=m;i++)
    {
        q[i].l = read(),q[i].r = read();
        if(st[q[i].l]>st[q[i].r])
        {
            swap(q[i].l,q[i].r);
        }
        int lcaa = lca(q[i].l,q[i].r);
        //具体判断询问的位置
        if(lcaa==q[i].l)
        {
            q[i].l = st[q[i].l];
            q[i].r = st[q[i].r];
            q[i].ll = q[i].l / B;
            q[i].rr = q[i].r / B;
            q[i].lca = 0;
        }
        else
        {
            q[i].l = ed[q[i].l];
            q[i].r = st[q[i].r];
            q[i].ll = q[i].l / B;
            q[i].rr = q[i].r / B;
            q[i].lca = lcaa;
        }
        q[i].id = i;
    }
    sort(q+1,q+1+m);
    int l = 1,r = 0;
    for(int i = 1;i<=m;i++)
    {
        //开莫，扩展区间
        while(l>q[i].l)
        {
            cala(dfn[--l]);
        }
        while(r<q[i].r)
        {
            cala(dfn[++r]);
        }
        while(l<q[i].l)
        {
            cala(dfn[l++]);
        }
        while(r>q[i].r)
        {
            cala(dfn[r--]);
        }
        //判断是否增加lca
        if(q[i].lca)
        {
            cala(q[i].lca);
        }
        ans[q[i].id] = anss;
        if(q[i].lca)
        {
            cala(q[i].lca);
        }
    }
    for(int i = 1;i<=m;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

另外，这道题比较卡常，具体的可以看我的警示后人。

五、二维莫队

二维莫队，顾名思义就是把一维的莫队再加一维度，维护一个矩阵的内容，所以其思路和普通莫队大致相似。

具体的以例题来讲解：

洛谷的 P1527 [国家集训队] 矩阵乘法：

这道题是正确做法是整体二分，但我们可以二维莫队写过，当然，这道题的一维版本是 P5356 [Ynoi Easy Round 2017] 由乃打扑克（不过~~带个修~~），写完了可以顺手水过。

这道题让我们求出一个矩阵的第 k 小值，因为 a_{i,j}\le 10^9，所以先对整个矩阵离散化，然后对询问二维排序，排序时可以按照左下、右上的 x,y 坐标依次排序，当然也可以像一维莫队一样奇偶化排序，具体见代码，其次一边维护一边进行值域分块（不会的先去学），最后分好块，暴力扫块求答案就可以了。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;

/*快读*/

//id是对于矩阵下标的分块，idd是对于离散化后的数的值域分块
//sum是对于离散化后的每个数的出现次数，sum_B是离散化后每个块对应数的出现次数之和
int n,m,a[510][510],ans[60010],b[250010],id[510],idd[250010],dB,B,tot;
int sum[250010],sum_B[510];

struct que
{
    int x0,y0,x1,y1,k,it;
    bool operator<(const que y) const
    {
        //仿照普通莫队的奇偶化排序
        if(id[x0]!=id[y.x0])
        {
            return x0 < y.x0;
        }
        if(id[y0]!=id[y.y0])
        {
            return (id[x0]&1)?(y0<y.y0):(y0>y.y0);
        }
        if(id[y1]!=id[y.y1])
        {
            return (id[y0]&1)?(y1<y.y1):(y1>y.y1);
        }
        return (id[y1]&1)?(x1<y.x1):(x1>y.x1);
    }
}q[60010];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    read(n),read(m);
    dB = n;
    for(register int i = 1;i<=n*n;++i)
    {
        idd[i] = (i-1) / n + 1;
    }
    for(register int i = 1;i<=n;++i)
    {
        //经过二分块长，取11是最优的，可以直接带进去减小常数
        id[i] = i / 11;
        for(register int j = 1;j<=n;++j)
        {
            read(a[i][j]),b[++tot] = a[i][j];
        }
    }
    //离散化
    sort(b+1,b+1+tot);
    tot = unique(b+1,b+1+tot) - b - 1;
    for(register int i = 1;i<=n;++i)
    {
        for(register int j = 1;j<=n;++j)
        {
            //这里不要手写二分，不如lower_bound（20次提交的教训）
            a[i][j] = lower_bound(b+1,b+1+tot,a[i][j]) - b;
        }
    }
    for(register int i = 1;i<=m;++i)
    {
        read(q[i].x0),read(q[i].y0),read(q[i].x1),read(q[i].y1),read(q[i].k),q[i].it = i;
    }
    //排序询问
    sort(q+1,q+1+m);
    //为了避免维护第一个，可以直接把第一个数带到矩阵里
    register int x0 = 1,y0 = 1,x1 = 1,y1 = 1;
    sum[a[1][1]] = sum_B[idd[a[1][1]]] = 1;
    for(register int i = 1;i<=m;++i)
    {
        //避免移动出错，可以先扩大再缩小
        while(y1<q[i].y1)
        {
            ++y1;
            for(register int j = x0;j<=x1;++j)
            {
                ++sum[a[j][y1]];
                ++sum_B[idd[a[j][y1]]];
            }
        }
        while(y0>q[i].y0)
        {
            --y0;
            for(register int j = x0;j<=x1;++j)
            {
                ++sum[a[j][y0]];
                ++sum_B[idd[a[j][y0]]];
            }
        }
        while(x1<q[i].x1)
        {
            ++x1;
            for(register int j = y0;j<=y1;++j)
            {
                ++sum[a[x1][j]];
                ++sum_B[idd[a[x1][j]]];
            }
        }
        while(x0>q[i].x0)
        {
            --x0;
            for(register int j = y0;j<=y1;++j)
            {
                ++sum[a[x0][j]];
                ++sum_B[idd[a[x0][j]]];
            }
        }
        while(y1>q[i].y1)
        {
            for(register int j = x0;j<=x1;++j)
            {
                --sum[a[j][y1]];
                --sum_B[idd[a[j][y1]]];
            }
            --y1;
        }
        while(y0<q[i].y0)
        {
            for(register int j = x0;j<=x1;++j)
            {
                --sum[a[j][y0]];
                --sum_B[idd[a[j][y0]]];
            }
            ++y0;
        }
        while(x1>q[i].x1)
        {
            for(register int j = y0;j<=y1;++j)
            {
                --sum[a[x1][j]];
                --sum_B[idd[a[x1][j]]];
            }
            --x1;
        }
        while(x0<q[i].x0)
        {
            for(register int j = y0;j<=y1;++j)
            {
                --sum[a[x0][j]];
                --sum_B[idd[a[x0][j]]];
            }
            ++x0;
        }
        //暴力扫块找到答案所在块
        register int cnt = 0,it = 1;
        while(cnt+sum_B[it]<q[i].k&&it<=idd[n*n])
        {
            cnt += sum_B[it];
            ++it;
        }
        //细扫一个块确定答案
        it = (it-1) * dB + 1;
        while(cnt+sum[it]<q[i].k&&it<=n*n)
        {
            cnt += sum[it];
            ++it;
        }
        ans[q[i].it] = b[it];
    }
    for(register int i = 1;i<=m;++i)
    {
        print(ans[i]),pc('\n');
    }
}

不过此题对于二维莫队极其卡常（我不会告诉你我交了 ~~101~~ 发）

六、莫队二次离线

看到这个算法题目，你可能会疑惑，莫队本身就是离线算法，为什么还会有二次的离线？

只是因为普通莫队的增加和删除点的操作是在线的，我们不妨设单次这两种操作所需的时间为 t(n)，则普通莫队的时间复杂度可以改写为 O(n\sqrt{n}t(n))，但如果 t(n) 是大于 1 的一个数，那么莫队算法的时间复杂度就无法保证，此时，如果我们给询问添加一个限制：可差分性，即一个区间的答案可以由多个区间取交集或并集而来，那么莫队二次离线就是以把询问的时间复杂度优化到：O(nt(n)+n\sqrt{m})

具体实现步骤如下：

首先，记一个下标为 x 的数 a_x 对于一个区间 [l,r] 的贡献为：f(x,l,r)，对区间 [1,r] 的贡献为：f(x,k)

那么利用可差分性，该数 a_x 对于区间 [l,r] 的贡献就可以改写为：f(x,r)-f(x,l-1)

设第一个询问区间为 [l_1,r_1]，接下来要转移的区间为 [l_2,r_2]，区间 [l,r] 的答案为 ans_{l,r}

接下来四种情况来讨论：

右端点右移：

即将答案从 ans_{l_1,r_1} 转移到 ans_{l_1,r_1+1}，其转移的贡献可以写为：
\begin{aligned} f(r_1+1,l_1,r_1+1) = - f(r_1+1,r_1+1) + f(r_1+1,l_1-1) \end{aligned}

减号左边的式子我们先放着，考将右边的式子的右端点扩展到 r_2，那么其所对应的贡献总和为：
\begin{aligned} \sum_{i=r_1+1}^{r_2}{f(i,i)-f(i,l_1-1)} \end{aligned}
这个式子的减号左边和上一个式子的减号左边有着异曲同工之妙，还是~~先放着~~。

那么我们主要求的贡献总和即为：
\begin{aligned} \sum_{i=r_1+1}^{r_2}{-f(i,l_1-1)} \end{aligned}
对于这个式子，它所对应的右端点是不变的，左端点对应的是一个区间，那么就可以从 r_1+1 到 r_2 递推或者扫描线或者加上一些数据结构做掉。
右端点左移

即将答案从 ans_{l_1,r_1} 转移到 ans_{l_1,r_1-1}，其转移的贡献可以写为：
\begin{aligned} -f(r_1,l_1,r_1) = - f(r_1,r_1) + f(r_1,l_1-1) \end{aligned}

减号左边的式子我们先放着，考将右边的式子的右端点缩小到 r_2，那么其所对应的贡献总和为：
\begin{aligned} \sum_{i=r_2+1}^{r_1}{-f(i,i)+f(i,l_1-1)} \end{aligned}
依然可以发现这个式子的减号左边和上一个式子的减号左边有着异曲同工之妙，还是~~先放着~~。

那么我们主要求的贡献总和即为：
\begin{aligned} \sum_{i=r_2+1}^{r_1}{f(i,l_1-1)} \end{aligned}
对于这个式子，它所对应的右端点是不变的，左端点对应的是一个区间，那么就可以从 r_2+1 到 r_1 递推或者扫描线或者加上一些数据结构做掉。
左端点右移

同上考虑得式子：
\begin{aligned} -f(l_1,l_1,r_1)=-f(l_1,r_1)+f(l_1,l_1-1) \end{aligned}
主要考虑：
\begin{aligned} \sum_{i=l_1}^{l_2-1}{f(i,i-1)-f(i,r_1)} \end{aligned}
剩余同上。
左端点左移

同上考虑得式子：
\begin{aligned} f(l_1-1,l_1-1,r_1)=f(l_1-1,r_1)-f(l_1-1,l_1-2) \end{aligned}
主要考虑：
\begin{aligned} \sum_{i=l_2}^{l_1-1}{f(i,r_1)-f(i,i-1)} \end{aligned}
剩余同上。

到此，我们把四种情况讨论完了，剩下的部分可以写作 \sum_{i=l}^{r}f(i,i) 或 \sum_{i=l}^{r}{f(i,i-1)}，这两个东西都是可以直接求出来的，总的时间复杂度就是 O(nt(n)+n\sqrt{m}) 了。

小结一下，莫队二次离线就是把莫队本身两个指针要移动的区间摘出来，再离线利用可差分性做掉，将原本的 t(n) 的时间拎出来，提升效率。

洛谷中对应的板子题号为 P4887 【模板】莫队二次离线，所对应的代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define intt __int128
#define endl '\n'

int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'||'9'<ch)
    {
        if(ch=='-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int inf = 1e18,N = 2e5 + 10,M = (1<<14);

int n,m,k,a[N],B,id[N],cnt[N],tot,cnt1[N];
int f1[N],f2[N],ans[N];

int get(int x)
{
    int sum = 0;
    while(x)
    {
        sum += (x%2);
        x>>=1;
    }
    return sum;
}

struct que
{
    int l,r,id;
}q[N];

struct node
{
    int l,r,op,id;
};

vector<node> itl[N],itr[N];

bool operator<(que x,que y)
{
    return (id[x.l]==id[y.l])?((id[x.l]&1)?(x.r<y.r):(x.r>y.r)):(id[x.l]<id[y.l]);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    n = read(),m = read(),k = read();
    if(k>14)
    {
        while(m--)
        {
            cout<<0<<endl;
        }
        return 0;
    }
    //提前处理有多少项的二进制下1的个数为k
    for(int i = 0;i<=M;i++)
    {
        if(get(i)==k)
        {
            cnt[++tot] = i;
        }
    }
    B = sqrt(n);
    for(int i = 1;i<=n;i++)
    {
        a[i] = read();
        id[i] = (i-1) / B + 1;
    }
    for(int i = 1;i<=m;i++)
    {
        q[i] = {read(),read(),i};
    }
    sort(q+1,q+1+m);
    //将莫队指针的移动区间“摘”出来
    for(int i = 1,l = 1,r = 0;i<=m;i++)
    {
        //像上文一样分四种讨论，既是判断区间，也是判断正负号
        if(r<q[i].r)
        {
            itl[l].push_back({r+1,q[i].r,1,q[i].id});
        }
        else if(r>q[i].r)
        {
            itl[l].push_back({q[i].r+1,r,-1,q[i].id});
        }
        r = q[i].r;
        //注意这里要先把右端点赋值了再把左端点加进去
        if(l<q[i].l)
        {
            itr[r].push_back({l,q[i].l-1,-1,q[i].id});
        }
        else if(l>q[i].l)
        {
            itr[r].push_back({q[i].l,l-1,1,q[i].id});
        }
        l = q[i].l;
    }
    //先预处理
    for(int i = 1;i<=n;i++)
    {
        f1[i] = cnt1[a[i]];
        for(int j = 1;j<=tot;j++)
        {
            ++cnt1[a[i]^cnt[j]];
        }
    }
    memset(cnt1,0,sizeof cnt1);
    for(int i = n;i;i--)
    {
        f2[i] = cnt1[a[i]];
        for(int j = 1;j<=tot;j++)
        {
            ++cnt1[a[i]^cnt[j]];
        }
    }
    memset(cnt1,0,sizeof cnt1);
    //再对莫队区间处理
    for(int i = 1;i<=n;i++)
    {
        for(int j = 0;j<itl[i].size();j++)
        {
            int l = itl[i][j].l,r = itl[i][j].r,id = itl[i][j].id,op = itl[i][j].op;
            for(int k = l;k<=r;k++)
            {
                ans[id] += op * (f1[k] - cnt1[a[k]]);
            }
        }
        for(int j = 1;j<=tot;j++)
        {
            cnt1[a[i]^cnt[j]]++;
        }
    }
    memset(cnt1,0,sizeof cnt1);
    for(int i = n;i;i--)
    {
        for(int j = 0;j<itr[i].size();j++)
        {
            int l = itr[i][j].l,r = itr[i][j].r,id = itr[i][j].id,op = itr[i][j].op;
            for(int k = l;k<=r;k++)
            {
                ans[id] += op * (f2[k] - cnt1[a[k]]);
            }
        }
        for(int j = 1;j<=tot;j++)
        {
            cnt1[a[i]^cnt[j]]++;
        }
    }
    memset(cnt1,0,sizeof cnt1);
    //把差分用前缀和统计起来，恢复回去
    for(int i = 1;i<=m;i++)
    {
        ans[q[i].id] += ans[q[i-1].id];
    }
    for(int i = 1;i<=m;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

七、莫队配合 bitset

一般来说，bitset 具有的优势是：空间小、区间运行速度快、支持位运算等，可以维护一些普通数据结构所较难维护的数值，同样，莫队也可以维护区间信息，将两者结合在一起则会使莫队算法更加简便和迅捷。

具体的用题目来举例子：

以洛谷中的 P4137 Rmq Problem / mex 这道题来作为例子。

这道题目询问我们一个区间 [l,r] 中没有出现过的最小自然数，如果暴力维护一个布尔数组最后统一查询的时间复杂度是 O(nm) 的显然不可以接受，但是~~我不想写分块~~怎么办？

这时候就要用到 bitset 了，在 bitset 中有一个重要的函数式 _Find_first，它的作用是返回当前 bitset 中第一个 true 的下标，那我们可以先把整个 bitset 赋为 1，然后把出现过的数赋为 0，最后用函数找一下就好，这样做的时间复杂度是 O(n\sqrt{n}+\frac{n^2}{w})，再加之奇偶化排序和吸氧就能过了。

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define intt __int128
#define endl '\n'

int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'||'9'<ch)
    {
        if(ch=='-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int inf = 1e18,N = 2e5 + 10;

int n,m,a[N],id[N],B,ans[N],sum[N];
bitset<N> falg;

struct que
{
    int l,r,id;
}q[N];

bool operator<(que x,que y)
{
    return (id[x.l]==id[y.l])?((x.r==y.r)?(0):((x.r<y.r)^(id[x.l]&1))):(x.l<y.l);
}

void add(int it)
{
    sum[a[it]]++;
    falg[a[it]] = 0;
}

void del(int it)
{
    sum[a[it]]--;
    if(sum[a[it]]==0)
    {
        falg[a[it]] = 1;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    n = read(),m = read();
    B = n / sqrt(m);
    for(int i = 1;i<=n;i++)
    {
        a[i] = read();
        id[i] = (i-1) / B + 1;
    }
    for(int i = 1;i<=m;i++)
    {
        q[i] = {read(),read(),i};
    }
    falg.set();
    sort(q+1,q+1+m);
    int l = q[1].l,r = q[1].l - 1;
    for(int i = 1;i<=m;i++)
    {
        while(r<q[i].r)
        {
            add(++r);
        }
        while(l>q[i].l)
        {
            add(--l);
        }
        while(l<q[i].l)
        {
            del(l++);
        }
        while(r>q[i].r)
        {
            del(r--);
        }
        ans[q[i].id] = falg._Find_first();
    }
    for(int i = 1;i<=m;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

八、总结

这篇文章算是对于我这半个多月的莫队学习的总结，具体做过的题后面有时间整理出来再发吧。

orz