浅谈回滚及其应用
hbhz_zcy
2022-09-25 16:31:23
## 引入
本文介绍并扩展了从一种回滚莫队引入的思想，回滚。
（目前这个东西还查不到，只能找到类似的思想[回退](https://baike.baidu.com/item/回退)和[回滚](https://baike.baidu.com/item/回滚)$^{[1]}$）
相信大家学习回滚莫队后会对这个东西记忆深刻：
```cpp
int stop=0,ston=0;
struct nodest{int *p;int v;}st[sqmaxn];
void add(int t){
...
for(...){
if(ston) st[++stop]={&f[i],f[i]};
f[i]=...;
}
if(ston) st[++stop]={&len,len};
len=...;
...
}
void recover(){for(ston=0;stop;stop--) *st[stop].p=st[stop].v;}
int main(){
...
while(tr<=r) add(a[++tr]);
ston=1;int _l=l/sqn*sqn-1;
while(l<=_l) add(a[l++]);
ans[q[i].id]=len;recover();
...
}
```
其中的`recover`函数就是回滚操作，但是与一般的回滚莫队有所不同。为了使回滚操作的适用范围更广，特意将其写为存地址和值的结构体，并以栈的形式实现。
## 特点
可以看出回滚操作就是十分暴力的把修改前的位置和压入栈中，回滚是就暴力地模拟恢复的过程。它的顺序与栈的顺序相同，故有正确性。
即使大家没有学过回滚莫队，大概也能明白其中的思想：进行一个主进程，期间有一些副进程，会产生修改，结束时把修改按顺序复原。
![图片]()
同时，它还有一些特点：
+ 栈所需的最大空间等于最大的所需回滚长度。
+ 回滚操作本身复杂度与压入一致，而压入操作复杂度与修改次数一致。因此回滚操作本身不会增加渐进时间复杂度，只会一定地增加常数。
这些性质非常优秀，简而言之一句话：可以不增加时间或空间复杂度。
## 改进
然而它的适用范围太狭窄了，于是我们再次进行修改：
+ 使用`ston`表示当前进行的版本号（表示当前的时间）。
+ 结构体里新增一个变量 $t$ 表示**被修改**的时间（可以理解为时间戳）。
+ 每次回滚时添加一个参数 $t'$ 表示一直滚 $\le t'$ 版本为止（因为标的是何时修改）。
显而易见的，现在的回滚可以顶半个可持久化，而且很适用于树形结构。
例：我们先在数组上进行这个操作：时间后拨一位，倒退到时刻 $t$，修改数组，查询数组。
```cpp
int N,M,a[maxn],stop=0,ston=0;
struct node{int *p;int v,t;}st[maxn];
void recover(int t){for(ston=t;st[stop].t>t;stop--) *st[stop].p=st[stop].v;}
int main(){
N=qd(),M=qd();
for(int i=1;i<=N;i++) a[i]=qd();
while(M--){
int c=qd(),x;
if(c==1) ston++;
else if(c==2) recover(qd());
else if(c==3) x=qd(),st[++stop]={&a[x],a[x],ston},a[x]=qd();
else printf("%d\n",a[qd()]);
}
return 0;
}
```
## 应用
其实真正有用的地方在树的dfs顺序上：
### 例1
暴力撤销并查集。
[线段树分治](https://www.luogu.com.cn/problem/P5787)：线段树保存并分治修改操作，其中使用了并查集互相连。
具体做法是按秩合并并查集并且进行逆操作拆并查集。实际上也可以带上路径压缩。
```cpp
...
st[++stop]={&...,...,ston};
...
void ask(int t,int l,int r){
ston=t;
...
ask(t<<1,ul,ur),ask(t<<1|1,ul,ur);
recover(t);
}
```
此处`ask`使用时间戳为 $t$ 是正确的，因为 $t$ 单调上升，且每次修改会直接版本覆盖。
注意：以上复杂度期望上是 $O(N\log(N))$ 的，但是均摊的时间复杂度会因为回退变得不正确，可以被卡掉。所以建议同时使用按秩合并，能将时间复杂度期望降成 $O(N\alpha(N))$，最差 $O(N\log(N))$。
### 例2
要求点带权的有根树维护从根节点到叶子节点的单调栈，每个叶子节点有查询。
第一想法显然是直接单调栈，每个节点开一个`vector`，把弹出的节点直接放里面，递归完再回复。
然而会很容易被一种蒲公英卡成暴力的 $\Theta(N^2)$：
这是因为到中心时的单调栈很长，每次访问子节点都会全部弹出，复杂度极大。
如果您会平衡树维护或者神奇的pb\_ds（这个比`vector`多支持分裂、合并），那就能轻松切掉这道题。
但是使用回滚也能轻松过掉，二分更新单调栈栈顶，新入栈记录并覆盖即可，常数还小得多。代码实现近似于暴力`dfs`。
```cpp
void dfs(int u){
vis[u]=1;st[++stop]={&ftop,ftop,u};
ftop=upper_bound(f+1,f+ftop+1,a[u])-f-1;
f[++ftop]=a[u];
if(!head[u]) ...;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(vis[v]) continue;
dfs(v);
}
recover();
}
```
$$\ $$
分析一下，可以看出树的dfs过程类似于最开始的例题，契合回滚的性质，空间开节点数即可，时间不会添加过多的消耗。因此这类回滚在树型结构中能很好的应用。
不过在应用时应当慎重考虑，因为指针使调试不方便，且常数的增加很可能是翻倍，比如线段树分治的扩展并查集`merge`部分:
```cpp
int mg(int x,int y){
int _x=fa(x+_maxn),_y=fa(y+_maxn);x=fa(x),y=fa(y);
if(x==y) return 1;
if(bv[x]<bv[y]) swap(x,y),swap(_x,_y);
st[++stop]={&bv[x],bv[x],ston};bv[x]+=bv[_y];
st[++stop]={&bv[_x],bv[_x],ston};bv[_x]+=bv[y];
st[++stop]={&b[y],b[y],ston};b[y]=_x;
st[++stop]={&b[_y],b[_y],ston};b[_y]=x;
return 0;
}
```
作者对回滚的拓展与应用只能想到这么多了，相信各位能够独立探索出更好的应用方法。
-----
参考文献：
\[1\]： [百度百科](https://baike.baidu.com)