一类撤销问题

Published: by Creative Commons Licence

  • Tags:

撤销的实现方式

如果一个操作对整体的改动很小,那么我们可以记录这个操作执行后的修改,并记录在案,之后就可以很方便的撤销这些修改。

比如所我们某个操作将$x$改变为$x+1$,那么我们只需要记录这个操作信息,之后在撤销的时候将$x$改变为$x-1$即可。但是不是所有操作都可以通过仅记录操作信息就能撤销的,比如chmin操作,将某个变量$x$修改为$\min(x,5)$,这样我们就不能简单的撤销这样的操作了。更加好用的方式是记录变量被修改前的状态,比如$x=x_0$,这样就能保证对任何操作都能执行撤销。

栈式撤销

撤销操作一般都需要栈式操作,即先完成的操作后撤销。这是非常重要的,因为后完成的操作可能依赖于先完成的操作带来的修改。比如创建对象,我们先创建一个对象$A$,之后创建一个对象$B$,并且$B$持有$A$。如果我们先撤销创建$A$这个操作,即销毁$A$,那么会导致销毁$B$的时候$A$已经不可用了。

栈式撤销是非常自然的,比如在树上进行DFS操作。于是在操作的时候我们每次函数返回后,所有的局部变量都会被销毁,而调用者的变量会恢复。

队列撤销

这篇内容基本来自[Tutorial] Supporting Queue-like Undoing on DS这篇文章,这里只是翻译和自己润色一下。

我们知道最自然的撤销方式是栈式的,但是如果题目要求你先撤销最旧的操作怎么办。这样的问题还是存在的,比如给定$n$个顶点,以及$m$条无向边,以及某个数$k$,要求为所有连续的$k$条边,计算在仅考虑这$k$条边的情况下有多少不同的连通分量。当然这个问题可以通过线段树+并查集在$O(n\log_2n\log_2m)$的时间复杂度内完成,也可以通过LCT在$O((n+m)\log_2(n+m))$的时间复杂度内解决。但是它们都是离线算法,我们接下来要讲一个可以泛化的在线算法,可以在$O(n\log_2n\log_2m)$的时间复杂度内解决这个问题。

我们先回到队列撤销这个话题中。首先我们很多时候只能撤销最近的操作,原因已经在栈式撤销一章中讲的很详细了,因此如果强行用队列撤销,那么就很难通用。

那么我们是否可以仅通过栈式撤销来实现队列撤销呢?如果操作满足交换性(即操作的执行顺序不影响结果),那么答案是可以的。下面讲一下做法。

考虑一种情况,所有操作都执行完成后,我们再逐一执行撤销。我们可以将所有操作存在栈中,之后我们出栈再重新入栈,这样就能翻转栈中的所有元素。这时候出栈就等价于出队列。

当然不是所有情况下都这么完美的,大部分时候执行操作和撤销操作是交错执行的。当然我们可以复用上面的思路,每次撤销之前,将栈中元素全部弹出,并重新排序后插回栈中,但是这会导致操作的执行次数和撤销次数达到$O(n^2)$。这太慢了。考虑上面过程中我们实际上栈中维护的是两种元素,一种是翻转过的,一种是没翻转过的,所有翻转过的元素都在没翻转过的元素之前执行。我们将前者记做$A$类操作,后者记做$B$类操作。下面我们讲一个更加快的算法。

  • 对于执行一个新操作,我们将操作作为$B$类操作入栈
  • 对于撤销一个操作。如果栈的顶部是$A$类操作,这显然是最旧的操作,我们直接出栈即可。否则,我们不断弹出栈顶元素,直到栈空或者弹出元素中$A$类和$B$类数目相同。之后调整顺序重新入栈,可以保证此时栈顶元素一定是$A$类的,这个过程我们称为修复。之后正常出栈即可。

下面我们证明上面这个过程中出栈和入栈次数的上限为$O(n\log_2n)$,其中$n$是操作总数。

证明如下:

我们发现上面所有操作的次数的复杂度都是线性的,除了修复过程。下面讨论修复过程。

一种情况是所有元素出栈,这时候我们会将所有$B$类元素转换为$A$类元素,因此我们可以估算出这阶段的入栈出栈次数上限为$O(n)$。

第二种情况是出栈的$B$类元素和$A$类元素数目相同,这时候出栈和入栈次数实际上是涉及的$B$类元素的数目的两倍,因此我们只需要讨论在修复过程实际出栈的$B$类元素总数即可。记$c_i$为第$i$次操作中修复过程且是第二种情况下,出栈的$B$类元素数目。因此第二种下入栈和出栈的次数为$O(\sum_{i=1}^nc_i)$。

这里我们需要发现一个重要的性质,对于任意$k$,如果存在$i\lt j$且$c_i,c_j\geq k$,那么一定有$j-i> k$。假设$j-i\leq k$,由于操作$j$一定是撤销,因此中间最多有$k-1$个操作,因此操作$j$中一定会出栈操作$i$出栈的$B$类元素中的一部分。设其中有$x$个出队操作,以及$k-1-x$个入队操作,那么由于$k-x>k-1-x$,因此不可能会出栈操作$i$出栈的$B$类元素,与假设相悖。

我们重写公式如下:

\[\begin{aligned} \sum_{i=1}^nc_i &=\sum_{i=1}^n\sum_{j=1}^n[c_j\geq i]\\ &\leq \sum_{i=1}^n\frac{n}{i}\\ &\approx n\ln n \end{aligned}\]

因此我们可以得出算法的时间复杂性上限为$O(n\log_2n)$次的出栈(撤销)和入栈操作(执行)。

并且如果请求为入栈出栈交替,那么就可以让出栈和入栈次数达到我们计算得到的上限。

回到我们一开始提到的问题,我们可以用不带路径压缩的并查集来实现栈式撤销,并且用上面的算法来保证操作和撤销次数为$O(m\log_2m)$,总的时间复杂度为$O(m\log_2n\log_2m)$,但是常数很小。

提供几道题目:

题目1:给定$n$条顶点,$m$条无向边,之后提供$q$个请求,第$i$个请求为$l_i,r_i$,要求回答仅考虑编号在$[l_i,r_i]$之间的边,判断所有顶点是否连通。其中$1\leq n, m\leq 10^5, 1\leq q\leq 10^6$

我们记$R(i)$表示最小的整数$j$,满足仅考虑编号在$[i,j]$之间的边,图连通。可以发现$R(i)$是个递增函数,因此我们可以通过撤销队列实现滑动窗口的效果,来预处理$R$。之后每个请求直接查表回答即可。时间复杂度为$O(m\log_2n\log_2m+q)$。

题目1:给定$n$条顶点,$m$条无向边,之后提供$q$个请求,第$i$个请求为$l_i,r_i$,要求回答仅考虑编号在$[l_i,r_i]$之间的边,判断所有顶点是否连通。其中$1\leq n, m\leq 10^5, 1\leq q\leq 10^6$

我们记$R(i)$表示最小的整数$j$,满足仅考虑编号在$[i,j]$之间的边,图连通。可以发现$R(i)$是个递增函数,因此我们可以通过撤销队列实现滑动窗口的效果,来预处理$R$。之后每个请求直接查表回答即可。时间复杂度为$O(m\log_2n\log_2m+q)$。

参考资料