一类撤销问题

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)$。

题目3:提供$n$个商品,第$i$件商品的价格为$w_i$,价值为$v_i$。我们总共有$m$单位金钱,希望能买到总价值最大的货物。换言之,我们希望选择一些商品,这些商品的总价格不超过$m$的前提下保证总价值最大。同时,如果我们同时购买$k$件物品,那么这$k$件物品中的一件我们可以免费以五折优化买走(如果价格不能整除2,则上取整),且上述优惠最多只能发生一次。问最大能取走的货物的总价值。其中$1\leq n,m\leq 3000$,$1\leq w_i,v_i\leq 10^9$,$1\leq k\leq n$。

这道题目,我们只需要理解了背包问题中加入新的商品这一操作也满足交换性,且很容易通过快照的方式进行撤销。因此我们只需要维护一个撤销队列,其中存放商品的一段前缀和后缀的背包信息即可。时间复杂度为$O(nm\log_2n)$。

非顺序撤销

现在考虑一组操作,如果它既不是栈式,也不是队列撤销的话该怎么办。

实际上类似于队列操作,如果操作满足交换性(操作的执行顺序不影响结果,只有是否被执行对结果有影响),那么我们可以通过离线请求后通过线段树来加速。

对于一个操作,其生效时间为其发生时间,其失效时间为其被撤销的时间。现在我们维护一个线段树,线段树结点$[L,R]$中存储所有生存时间覆盖这个区间的操作。这样我们发现任意一次操作最多会同时出现在$O(\log_2n)$个线段树结点中。

接下来对于结果的查询,我们可以在线段树上DFS,当我们遍历到顶点$v$的时候,将$v$中的所有操作全部应用,在离开顶点$v$的之后,将$v$中的所有操作全部回退。可以发现上述的所有操作都是栈式的,而所有操作栈式都是可以支持回退的。当我们遍历到线段树的叶子顶点$[i,i]$的时候,现在的状态等价于执行了所有发生在$i$之前,且未被撤销的操作的状态。我们直接统计结果即可。

上面的过程中每个操作都最多被执行和撤销$O(\log_2n)$次。可以发现这个结果和队列式撤销是一致的,而且大部分时间队列式撤销也可以通过这个技术来解决,当然不要忘记队列式撤销的优势是它支持在线操作。

题目1:给定$n$个物品,第$i$件物品的价值为$v_i$,重量为$w_i$。之后考虑$q$个请求。每个请求要么新增一个物品,要么删除一个物品,要么查询容量为$k$的背包最大能装走的物品总价值。其中$1\leq n,q\leq 10^4$,$1\leq k\leq 10^3$。

提供一道题目

如果没有删除,实际上这个问题只是一个简单的背包DP。这里的难点实际上删除带来的。并且由于题目中没有说明用的是队列还是栈式删除,因此我们也不能直接应用这些撤销技术。

我们可以直接用上面提到的线段树的技术解决这个问题。时间复杂度为$O(k(n+q)\log_2n)$。

题目2:给定一副$n$个顶点没有边的无向图。之后处理$q$个请求,第$i$个请求要么删除一条边,要么加入一条边,要么查询两个顶点之间是否存在一条路径。其中$1\leq n,m\leq 10^5$。

由于不带路径压缩的DSU也是支持栈式撤销的,因此可以直接用上面提到的技术,时间复杂度为$O(q\log_2n\log_2q)$。

参考资料