回滚莫队 学习笔记

前置知识

• 普通莫队

算法

需要回滚莫队的问题一般不好增加或不好删除一个位置。
假设，现在我们维护的东西可以 $\mathcal O\left(1\right)$ 缩小区域，但是增加区域需要 $\mathcal O\left(n\right)$。
为了防止增加，我们可以将每个操作的右边界从大到小排序。

假设现在莫队维护的区域是 $\left[L, R\right]$，我们第一步需要缩小右边界。
考虑左边界。左边界是分块的，首先我们要求出从当前块的左边界到最右边的答案。
对于每次操作，我们可以在缩小的过程中记录修改信息，在调整完毕后依据记录的修改信息回滚。

复杂度

对于每个左边界的块：

1. 初始计算答案：$\mathcal O\left(n\right)$
2. 右界移动：总共最多 $n$ 次，$\mathcal O\left(n\right)$

对于每个询问

1. 移动边界：$\mathcal O\left(\sqrt n\right)$
2. 回滚边界：$\mathcal O\left(\sqrt n\right)$

总复杂度：$\mathcal O\left(n\right) + \mathcal O\left(n \sqrt n\right) + \mathcal O\left(Q \sqrt n\right) = \mathcal O\left(\left(n + Q\right) \sqrt n\right)$，其中 $Q$ 是询问次数。

例题 1

题意

区间 $\operatorname{mex}$，即最小的未出现正整数。

题解

我们先分析一下 有什么性质：
设 $c\left(x\right)$ 表示当前维护的区间中 $x$ 的出现次数。
设 $t$ 为当前维护区间中的 $\operatorname{mex}$。

• 当扩大边界时：

  • 如果新加入的数小于 $t$：不对答案造成影响，直接修改出现次数即可。复杂度 $\mathcal O\left(1\right)$
  • 如果新加入的数大于 $t$：不对答案造成影响，直接修改出现次数即可。复杂度 $\mathcal O\left(1\right)$
  • 如果新加入的数等于 $t$：修改出现次数，并且对答案造成影响，需要往后查找下一个未出现的数。复杂度 $\mathcal O\left(n\right)$

所以可以发现，扩大边界需要 $\mathcal O\left(n\right)$ 的时间。

• 再看看缩小：

  • 如果删除的数大于 $t$：不对答案造成影响，直接修改出现次数即可。复杂度 $\mathcal O\left(1\right)$
  • 如果删除的数等于 $t$：这种情况不可能，因为 $t$ 没有出现过。复杂度 $\mathcal O\left(1\right)$
  • 如果删除的数小于 $t$：如果删没了，就更新 $t$，否则不对答案造成影响，直接修改出现次数即可。复杂度 $\mathcal O\left(1\right)$

所以可以发现，缩小边界只需要 $\mathcal O\left(1\right)$ 的时间。
然后，就跟 §算法§ 里说的一模一样了。

---

Background Knowledge

• Normal Mo's algorithm

Algorithm

Problems requiring the use of rollback Mo's algorithm are generally not easy to add or delete a location
Assume that the thing we maintain can shrink the region in $\mathcal O\left(1\right)$ time, but expanding the region requires $\mathcal O\left(n\right)$ time.
To prevent expansion, we can sort the right endpoints of each operation from large to small.

Assume that the region maintained by Mo's algorithm is $\left[L, R\right]$, and the first step we need to take is to shrink the right endpoint.
Consider the left endpoint. The left endpoint is partitioned, and first, we need to calculate the answer from the left endpoint of the current block to the rightmost endpoint.
For each operation, we can record the modification information during the shrinking process and roll back according to the recorded modification information after adjustment.

Complexity

For each block of the left endpoint:

1. Initial calculation of the answer: $\mathcal O\left(n\right)$
2. Moving the right endpoint: At most $n$ times in total, $\mathcal O\left(n\right)$
   For each query:

Moving the boundary: $\mathcal O\left(\sqrt n\right)$

1. Rolling back the boundary: $\mathcal O\left(\sqrt n\right)$
2. Total complexity: $\mathcal O\left(n\right) + \mathcal O\left(n \sqrt n\right) + \mathcal O\left(Q \sqrt n\right) = \mathcal O\left(\left(n + Q\right) \sqrt n\right)$, where $Q$ is the number of queries.

Example 1

Problem Statement

Find the minimum positive integer that does not appear in the interval.

Solution

Let's analyze the properties first:
Let $c\left(x\right)$ denote the number of times $x$ appears in the current interval being maintained.
Let $t$ be the $\operatorname{mex}$ in the current interval being maintained.

• When expanding the boundary:

  • If the newly added number is less than $t$: it does not affect the answer, just modify the occurrence frequency. Complexity is $\mathcal O\left(1\right)$.
  • If the newly added number is greater than $t$: it does not affect the answer, just modify the occurrence frequency. Complexity is $\mathcal O\left(1\right)$.
  • If the newly added number is equal to $t$: modify the occurrence frequency, and it affects the answer, we need to look for the next unappeared number. Complexity is $\mathcal O\left(n\right)$.
    Therefore, it can be found that expanding the boundary requires $\mathcal O\left(n\right)$ time.

• Let's take a look at shrinking:

  • If the deleted number is greater than $t$: it does not affect the answer, just modify the occurrence frequency. Complexity is $\mathcal O\left(1\right)$.
  • If the deleted number is equal to $t$: this is impossible because $t$ has never appeared. Complexity is $\mathcal O\left(1\right)$.
  • If the deleted number is less than $t$: if it is deleted, update $t$, otherwise it does not affect the answer, just modify the occurrence frequency. Complexity is $\mathcal O\left(1\right)$.
    Therefore, it can be found that shrinking the boundary only requires $\mathcal O\left(1\right)$ time.
    Then, it is exactly the same as what is mentioned in §Algorithm§.

---

• 分类： 学习笔记
• 最后更新于：2024-06-30 01:47:21^UTC+8
• 标签： 莫队