一类撤销问题

Published: October 11, 2020 by Daltao

• Categories:
• algorithm 101

• 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)$，但是常数很小。

提供几道题目：

• https://codeforces.com/contest/1423/problem/H
• https://codeforces.com/contest/1386/problem/C

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

参考资料

• [Tutorial] Supporting Queue-like Undoing on DS