浅谈普通莫队

· · 算法·理论

本文章同步发表在博客园。

什么是普通莫队？

莫队，是莫涛发明的一种解决区间查询等问题的算法，基于分块思想，时间复杂度为 O(n \sqrt{q})。

该文仅介绍普通莫队。

通常的莫队题目都需要离线操作。如果题目强制在线就不能用莫队做了喵！

当题目可以在已知区间 [l,r] 的答案的情况下 O(k) 求出 [l,r+1],[l+1,r],[l,r-1],[l-1,r] 的答案（即相邻区间的答案），就可以用莫队在 O(kn\sqrt{q}) 的时间复杂度下求出所有 q 个询问分别的答案了。

通常 k 为 1，有时为 \log n。

普通莫队怎么做？

首先你肯定要想好如何快速求出相邻区间的答案，例如统计区间不同数字个数，可以用桶维护。

知道怎么求相邻区间答案还不够，因为你在查询的时候可能会在序列两端“左后横跳”，到头来可能都不如暴力。因此我们想到要优化。

导致查询的时候乱跳的原因是什么？显而易见，因为我们查询的顺序是乱的。如果对所有查询按照某种顺序排列，是不是就能让它少跳一点，速度也就快一些呢？

当然可以，但问题在于你要怎么排序。很容易想到以 l 为第一关键词、r 为第二关键词分别升序排序，但是这样做效果并不好，甚至依然不如暴力。

这里就不得不提到莫涛大神了。他给出的方法是——分块！

分块后，每个元素 i 都有它所属的块 bel_i 了，我们再按照 bel_l 为第一关键词，bel_r 为第二关键词排序。

为啥这样复杂度就能下降？那就来算算复杂度吧。对于 l，相邻两个区间移动的距离不会超过块长 B；对于 r，每个块的所有区间总共移动的距离不会超过序列总长度 n。假设询问 q 次，则左端点移动次数为 qB，右端点移动次数为 \frac{n^2}{B}，不难发现当 B 取 \sqrt{\frac{n^2}{q}} 时总移动次数最少。

此时，我们的时间复杂度均摊是 O(n \sqrt{q}) 的，能够通过 10^5 规模的题目了。说是有的时候 10^6 也能冲过去呢。

盗用借用知乎上某篇文章的动图展示一下莫队的移动过程。

我们发现这个过程中，当 l 移动到别的一个块中，r 都得左移好长一段，你不觉得这样非常浪费时间吗？是的，所以这里出现了一个优化：奇偶化排序。它是一个常数优化，表示，当 bel_l 是奇数时，若 l 相等，则按 r 升序排序，否则按 r 逆序排序。

这样能带来怎样的好处呢？来看看优化后的移动过程吧：

可以发现，当 l 在偶数块时，r 在往回走的过程中就能够把答案都算出来。这样就比原来没优化的做法快了整整一倍呀！还是很不错的吧。

这就是普通莫队做法的整个过程啦。

如何实现普通莫队？

莫队的核心其实在于 Add 和 Del 两个函数，其他部分基本都是一样的，直接套板子即可。

Add 和 Del 是两个什么函数？它们是用来计算相邻区间答案的函数。Add 函数有一个传参 p，表示这一轮移动把元素 p 纳入了区间中；Del 函数同样有一个传参 p，但含义不一样——相信你已经猜到了，这里是表示这一轮移动把元素 p 移出了区间。其处理方式一般都比较相似。

其他地方，一般就是相同的了：读入所有数组元素信息和查询信息——重点是查询，然后把查询信息排序（还是比较建议加上奇偶化排序这个优化的），最后就是愉快的莫队环节啦。

放一下一般可以直接套板子的代码。Add 和 Del 因题而异就不放了哈。

m=read();//m 是询问次数
for(int i=1;i<=m;i++)
    q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++){
    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]=nowAns;
    //nowAns 表示“当前答案”
    //是 Add 和 Del 函数的重点维护对象
}for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";

例题讲解

P3901 数列找不同

用桶维护区间不同数字个数，然后每次看这个个数是否等于区间长度即可。

void Add(int p){
    if(!c[a[p]])nowAns++;
    c[a[p]]++;return;
}
void Del(int p){
    if(c[a[p]]==1)nowAns--;
    c[a[p]]--;return;
}

P8773 选数异或

依然维护桶，但是更新 \text{nowAns} 时需要看 a_p \oplus X 的值的个数。至于为什么要 \oplus X 相信大家都知道吧，异或的性质。

void Add(int p){
    nowAns+=c[a[p]^X];
    c[a[p]]++;return;
}
void Del(int p){
    nowAns-=c[a[p]^X];
    c[a[p]]--;return;
}

P2709 莫队 / 小B的询问

依然维护桶，但在每次更新 \text{nowAns} 时，最好先让 \text{nowAns} 减去 {c_{a_p}}^2，修改 c_{a_p} 之后再让 \text{nowAns} 加上 {c_{a_p}}^2。当然你套数学公式也是可以的只是没啥必要。

void Add(int p){
    nowAns-=c[a[p]]*c[a[p]];c[a[p]]++;
    nowAns+=c[a[p]]*c[a[p]];return;
}
void Del(int p){
    nowAns-=c[a[p]]*c[a[p]];c[a[p]]--;
    nowAns+=c[a[p]]*c[a[p]];return;
}

CF86D Powerful array

与上一题十分类似，只是加减的是 {c_{a_p}}^2 \times a_p。

void Add(int p){
    nowAns-=c[a[p]]*c[a[p]]*a[p];c[a[p]]++;
    nowAns+=c[a[p]]*c[a[p]]*a[p];return;
}
void Del(int p){
    nowAns-=c[a[p]]*c[a[p]]*a[p];c[a[p]]--;
    nowAns+=c[a[p]]*c[a[p]]*a[p];return;
}

P1997 faebdc 的烦恼

不同于之前只需要一个桶 c 来记录每种数字出现的个数，这里还需要一个 cnt 数组记录某种出现次数对应的数字个数。Add 时直接更新，Del 时需要判断如果当前删除的是唯一的最优解了，就要让答案 -1。因为原来的最优解的个数也只是 -1 了而已，这不可能不是当前的最优解，只是可能有多种情况罢了。

void Add(int p){
    cnt[++c[a[p]]]++;
    if(c[a[p]]>nowAns)nowAns=c[a[p]];return;
}
void Del(int p){
    if(cnt[c[a[p]]]==1&&nowAns==c[a[p]])nowAns--;
    cnt[c[a[p]]--]--;return;
}

CF617E XOR and Favorite Number

异或区间和也可以用前缀和的思想求，s_i 表示 a_1 \oplus a_2 \oplus \dots \oplus a_i 的值，那么算区间 [l,r] 的异或和就是 s_r \oplus s_{l-1}。每次修改 \text{nowAns} 的时候直接看桶里数字 s_p \oplus k 的个数就可以了。注意你需要对这里输入进来的查询的 l \gets l-1。

void Add(int p){
    nowAns+=c[sum[p]^k];
    c[sum[p]]++;return;
}
void Del(int p){
    c[sum[p]]--;
    nowAns-=c[sum[p]^k];return;
}

P4137 Rmq Problem / mex

Add 和 Del 函数只需用桶维护每种数字的出现个数，并不需要记录 \text{nowAns}，求 \operatorname{mex} 算 \text{nowAns} 的时候再找桶中第一个没出现的即可。但是这样会跑的比较慢，所以可以把桶的是否出现映到一个 bitset 里，查询时用 ._Find_first() 函数即可。注意 ._Find_first() 是找第一个为 1 的位置，而我们是要找第一个没出现的，所以在 bitset 中需要把出现了的标为 0，没出现的标为 1。

void Add(int p){
    c[a[p]]++;
    if(c[a[p]]==1)bt.set(a[p],0);return;
}
void Del(int p){
    c[a[p]]--;
    if(!c[a[p]])bt.set(a[p],1);return;
}

ans[q[i].id]=bt._Find_first();
//这一行是下面执行莫队操作后记录答案处的代码

P7764 Poklon

依然用桶维护，只是在这里同步维护的 \text{nowAns} 是记录出现次数恰好为 2 的数有多少个了。

void Add(int p){
    if(c[a[p]]==2)nowAns--;c[a[p]]++;
    if(c[a[p]]==2)nowAns++;return;
}
void Del(int p){
    if(c[a[p]]==2)nowAns--;c[a[p]]--;
    if(c[a[p]]==2)nowAns++;return;
}

P14046 BaoBao Loves Reading

考虑每本书在哪些 k 的情况下，BaoBao 需要去书架上拿书。

首先，如果这本书在整个阅读计划中是第一次出现，那么 BaoBao 肯定需要去书架上拿书，因为不管书桌有多大，因为是第一次出现，这本书肯定也在书架上面。

否则，找到这本书在阅读计划中上一次出现的位置，统计这中间有多少本不同的书，注意不能算当前这本书。如果这个数量 \ge k，那么这个 k 就是需要去拿这一本书的。

于是，问题就转化为求若干个区间中不同书的数量，并且这些区间最多也就 n 个。不难发现这可以莫队轻松解决。求出这些数量之后，维护差分即可算出每个 k 对应的取书次数啦。

void Add(int p){if(!c[a[p]])nowCnt++;c[a[p]]++;return;}
void Del(int p){if(c[a[p]]==1)nowCnt--;c[a[p]]--;return;}

n=read(),m=0,L=1,R=0;
sq=sqrt(n),Bas=0,nowAns=0,cnt=0;//多测清空
for(int i=1;i<=n;i++)ans[i]=0,c[i]=0;
for(int i=1;i<=n;i++)a[i]=read(),g[a[i]].pb(i);
for(int x=1;x<=n;x++){
     if(g[x].size()>0)Bas++;
     if(g[x].size()<2)continue;
     for(int i=0;i<g[x].size()-1;i++)
         q[++m]={g[x][i],g[x][i+1]};
}sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++){
    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[1]++,ans[nowAns]--;
    //由于我的代码里，区间包含了当前这本书
    //因此 nowAns 求出的其实是包含不同书本数量 +1
    //那么在维护差分的时候直接让 ans[nowAns]-- 即可
}for(int i=1;i<=n;i++)ans[i]+=ans[i-1];
for(int i=1;i<=n;i++)
    cout<<ans[i]+Bas<<" ";cout<<"\n";
for(int i=1;i<=n;i++)g[i].resize(0);//多测清空

总结

莫队，是由莫涛大神发明的一种离线算法，其可以在 O(kn \sqrt{n}) 时间复杂度下求出一系列区间的某种数值情况。通常情况下，要使用莫队算法，必须能通过一个区间的答案 O(k) 地求出与之相邻的区间（即多一个或少一个数字）的答案，一般 k=1 有时 k=\log n。其用处非常广泛，如维护区间不同数值个数、区间中和为某定值的子序列数量等等。总之，它是一个非常好用的用于解决区间问题的根号算法喵！

码这么多字也不容易，留个赞支持一下好嘛谢谢啦 qwq > <