一类撤销问题

Published: by Creative Commons Licence

  • Tags:
  • Table

撤销的实现方式

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

比如所我们某个操作将$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)$。

优先队列撤销

了解了队列撤销后,会发现在实际情况下队列撤销并不是很使用,因为大部分情况,撤销操作都是乱序的。

现在考虑如果我们能提前知道撤销操作的发生的顺序,那么就可以利用优先队列撤销来解决。

这里是原文地址[Tutorial] Supporting Priority-Queue-like Undoing on DS

优先队列撤销是指我们要维护一个优先队列,所有的操作都带有优先级。优先队列支持两类行为:

  1. 应用某个操作
  2. 撤销优先级最高的操作

具体的实现非常简单。我们维护一个栈,当一个操作入栈时,我们就应用这个操作,当一个操作出栈时,我们就将这个操作撤销。

之后对于行为1,我们直接将操作加入到栈顶即可。而对于操作2,这里要特殊处理。最简单的方式是我们把所有的栈中元素弹出,重新排序后按照优先级从低到高插入到栈中。但是这样会带来非常糟糕的时间复杂度。这里我们采用另外一种巧妙的方法,我们找到最小的正整数$k$,使得栈顶的$k$个元素中,同时包含了栈中优先级最高的$C(k)=\lceil k/2\rceil$个操作,这样的$k$是一定存在的。之后我们将前$k$个元素弹出,并且将优先级较低的元素先按照任意顺序插回到栈中,而优先级最高的$C(k)$个元素则之后按照优先级从低到高依次插入到栈中。

为了方便实现,同时为了减少时间复杂度,我们可以为每个操作维护它们在栈中距离栈底的偏移量,同时维护一个包含所有栈中元素的有序集合(二叉平衡树)。之后对于撤销我们只需要枚举有序集合的前面$C(k)$个元素即可,这样我们顺带还能避免显式对这$C(k)$个元素进行排序从而恶化时间复杂度。

可以发现插入操作会带来$O(\log n)$的时间复杂度,同时一次操作的执行。而撤销操作会带来$O(\log N+k)$的时间复杂度以及$k$次操作的撤销执行。

现在我们来计算撤销操作的摊还时间复杂度。

命题:假设第$i$次操作和第$j$次操作都是撤销操作,二者出栈的元素数目分别为$c_i$和$c_j$,且$i<j$,那么$2(j-i)\geq \min(c_i,c_j)$

令$k=\min(c_i,c_j)$,考虑$j-i<\frac{k}{2}$。在完成第$i$次操作后,优先级最高的$C(k)-1$个元素放置在栈顶,记这些元素构成的集合为$U$。记$i$和$j$之间插入操作数为$m$,很多显然$U$中至少有$C(k)-1-(j-i-1-m)=C(k)+m-(j-i)>m$个元素。因此在第$j$次操作时,至多弹出顶部的$2m\leq 2(j-i-1)<k-2$个元素,这与$c_j\geq k$相悖,因此假设不成立。

利用这个命题可以直接得到时间复杂度,这里如果第$t$次操作不是撤销操作,则定义$c_t=0$

\[\sum_{i=1}^nc_i=\sum_{t=1}^n\sum_{i=1}^n[c_i\geq t]\leq \sum_{t=1}^n\frac{n}{t}=O(n\ln n)\]

因此可以证明每次撤销操作所应用和取消的操作数的摊还数量为$O(\log n)$。因此优先队列撤销的时间复杂度为

  1. 插入操作:$1$次操作应用,并附加$O(\log n)$时间复杂度。
  2. 删除操作:$O(\log n)$次操作应用和取消,并附加$O(\log n)$时间复杂度。

非顺序撤销

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

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

对于一个操作,其生效时间为其发生时间,其失效时间为其被撤销的时间。现在我们维护一个线段树,线段树结点$[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)$。

参考资料