莫队

发布于 2021-04-22  1.97k 次阅读


由于本人比较菜,本文只会讲解较简易的莫队算法。
由于讲解需要,本文的准备时间不是很长,本文采用的是本人以前做过的题目和以前写的代码。

普通莫队

例题

我们借助模板题来讲解莫队算法: [国家集训队]小Z的袜子

简要地说,给出一个长为 $n$ 的序列 $a$,同时有 $q$ 组询问,每组询问给出一对下标 $l,r$,问你等概率取两个数 $l \le x,y \le r$,$a[x] = a[y]$ 的概率。

$1 \le a_i < n,q \le 50000$

分析

显然你只需要求出 $a[l] \sim a[r]$ 之间每种值的出现次数就可以算出询问的答案了。

这里讲解莫队做法。

由于对每一个询问遍历区间内的全部元素会让复杂度爆炸。考虑离线所有的询问,我们先暴力求出第一个区间所对应的答案,然后借助这次求出的部分信息在较短的时间内推出第二个区间所对应的答案,以此类推。

我们发现在求出区间 $[l,r]$ 所对应的答案后,我们可以在 $O(1)$ 的复杂度下推出 $[l+1,r],[l-1,r],[l,r+1],[l,r-1]$ 这些区间的值。

所以我们可以写出下面的代码来解决这个问题。

请注意:在莫队处理中你需要时刻保证 $l \le r + 1$,建议先扩大区间,再减小区间,即顺序依次为 l--,r++,l++,r--

void add(int p) {
    // 加上 a[p] 带来的贡献
}
void del(int p) {
    // 减去 a[p] 带来的贡献
}
double getAns(void) {
    // 得到当前状态下的答案
}

int l = 1, r = 0;
for (register int i = 1; i <= q; i++) {
    while (l > ask[i].l) add(--l);
    while (r < ask[i].r) add(++r);
    while (l < ask[i].l) del(l++);
    while (r > ask[i].r) del(r--);
    ans[ask[i].id] = getAns();
}

但是显然该做法复杂度为 $O(n^2)$,依旧无法通过本题。

优化 1

考虑将所有区间以左端点为第一关键字,右端点为第二关键字排序,排序后再进行上述莫队操作。

该做法会比优化前快不少,但是在最坏情况下仍旧为 $O(n^2)$。

优化 2

考虑优化 1 中左端点移动次数是 $O(n)$ 的,但是右端点移动次数最高可到达 $O(n^2)$ 次,考虑降低右端点移动次数并允许适度增加左端点移动次数。

考虑将 $1 \sim n$ 划分为 $\sqrt n$ 块。对所有区间排序,排序过程中对于两个区间,若它们左端点所在块不同,则左端点所在块编号小的区间排在前面;若他们左端点所在块相同,则右端点小的区间排在前面。

考虑后面的莫队操作过程中左右端点分别的移动次数。

对于左端点:共 $O(q)$ 个询问,每个询问左端点移动次数为 $O(\sqrt n)$,所以左端点一共移动了 $O(q \sqrt n)$ 次。
对于右端点:对于所有左端点在同一块中的询问,右端点移动次数为 $O(n)$。而总块数为 $O(\sqrt n)$,所以右端点一共移动了 $O(n \sqrt n)$。

由于本题中左右端点移动一次的复杂度为 $O(1)$,所以优化后的时间复杂度为 $O((n + q) \sqrt n)$。

优化 3

在优化 2 中左端点在同一个块中的区间按照右端点排序。在后面的莫队操作中,当处理到左端点在某一块中的最后一个区间时,右端点为一个较大的数。而再处理下一个区间的时候,左端点在下一个块内了,右端点由于从小到大排序,也可能较小。此时右端点需要花最多 $O(n)$ 次移动才能到达新的右端点。

我们假设所有块的编号为 $1,2,3\dots$,则我们考虑在排序的时候,对于左端点不在同一个块内的区间,依旧让左端点所在块编号较小的区间在前面;而当左端点位于同一个块内时,若左端点所在块的编号为奇数,则让右端点从小到大排序;若左端点所在块的编号为偶数,则让右端点从大到小排序。

在最坏情况下此优化可以比优化前节省 $O(n \sqrt n)$ 的移动次数。

代码

AC 代码

代码采用了优化 2 和优化 3。

习题

  1. 小B的询问我的代码
  2. 大爷的字符串题我的代码

带修莫队

即在普通莫队的基础上加入修改操作。

例题

[国家集训队]数颜色 / 维护队列

简要题意:给出一个长为 $n$ 的序列 $a$,和 $q$ 组操作。每组操作可以为 1. 修改 $a[i]$ 的值;2. 查询 $a[l] \sim a[r]$ 之间出现过多少个不同的值。

分析

将修改和查询分开来存放,同时对每个查询记录一个时间刻,即该查询之前的修改的数量。

排序仍按照 优化 2优化 3 进行。

在进行莫队操作的时候同样需要对时间刻进行莫队处理。

void add(int p) {
    // 加上 a[p] 带来的贡献
}
void del(int p) {
    // 减去 a[p] 带来的贡献
}
double getAns(void) {
    // 得到当前状态下的答案
}

int l = 1, r = 0, t = 0;
for (register int i = 1; i <= q; i++) {
    while (l > ask[i].l) add(--l);
    while (r < ask[i].r) add(++r);
    while (l < ask[i].l) del(l++);
    while (r > ask[i].r) del(r--);
    while (t < ask[i].t) {
        if (l <= opt[t].pos && opt[t].pos <= r) del(opt[t].pos);

        // 将 a[opt[t].pos] 的值改为进行该修改后的值

        if (l <= opt[t].pos && opt[t].pos <= r) del(opt[t].pos);
    }
    while (t > ask[i].t) {
        if (l <= opt[t].pos && opt[t].pos <= r) del(opt[t].pos);

        // 将 a[opt[t].pos] 的值改为进行该修改前的值

        if (l <= opt[t].pos && opt[t].pos <= r) add(opt[t].pos);
    }
    ask[i].ans = getAns();
}

代码

AC 代码

习题

待补

莫队配合 bitset

bitset 常用于常规数据结构难以维护的的判定、统计问题,而莫队可以维护常规数据结构难以维护的区间信息。把两者结合起来使用可以同时利用两者的优势。 —— OI Wiki

这类题的难点我认为一般在于想到如何把莫队与 bitset 结合。

例题

[Ynoi2016] 掉进兔子洞

简要题意:给出一个长为 $n$ 的序列 $a$,接着有 $q$ 组询问。每组询问给出三个区间,把三个区间中同时出现的数一个一个删掉,问最后三个区间剩下的数的个数和。

$1 \le n,m \le 10^5,1 \le a_i \le 10^9$

分析

容易发现最终答案为三个区间的长度和减去每个数字在三个区间内出现的最小次数。

显然我们可以把每个询问拆分为三个子询问,在 $3 \times q$ 个询问全做完后再合并子询问答案得到最终结果。

如果按照以往的记录区间内每个值的出现次数,则无法在较小的时间复杂度内统计答案。

考虑到上面这个方法的一个特别之处:所有值的出现次数之和不超过 $n$。

则我们在离散化时不进行去重操作,即对于每个值,它在原序列中出现了几次,在离散化后的序列中也出现了几次。然后开一个长为 $n$ 的 bitset,同时对离散化后的每个值 $i$ 记录其第一次出现的位置 $pos[i]$。

然后在莫队过程中,我们若加入一个值为 $val$ 的数,则令 bitset 的 pos[i] 位变成 $1$ 且 pos[i]++;我们若删除一个值为 $val$ 的数,则令 bitset 的 pos[i] 位变成 $0$ 且 pos[i]--

最后对于每个子询问,记录其对应的 bitset。最后合并子询问时只需要把每个子询问对应的 bitset or 起来,统计得到的 bitset 中的 $1$ 的数量即为所有数在三个区间内出现的最少次数之和,即可推出答案。

代码

毕竟是 Ynoi,这道题比较卡时间,可能需要把 $q$ 组询问分段处理。同时可能要特别注意一些操作的常数优化。

代码

习题

  1. 小清新人渣的本愿我的代码
  2. [Ynoi2017] 由乃的玉米田
  3. [Ynoi2011] WBLT

树上莫队

待补

回滚莫队

待补


我缓慢吐出一串啊吧啊吧并不再想说话