浅谈回滚及其应用

引入

本文介绍并扩展了从一种回滚莫队引入的思想，回滚。
（目前这个东西还查不到，只能找到类似的思想回退和回滚^{[1]}）
相信大家学习回滚莫队后会对这个东西记忆深刻：

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，修改数组，查询数组。

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

暴力撤销并查集。
线段树分治：线段树保存并分治修改操作，其中使用了并查集互相连。
具体做法是按秩合并并查集并且进行逆操作拆并查集。实际上也可以带上路径压缩。

...
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。

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部分:

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]： 百度百科