可持久化数据结构

众所周知，在竞赛界有这么一种神奇的解决方案，用以解决简单数据结构无法恢复历史版本的问题。

它就是可持久化！

如何可持久化？当然是要记录历史信息了。

但是那消耗空间不会巨大吗？

起始如果我们可以合理运用历史版本信息，我们就可以在创建新版本的时候尽可能地缩减需要的空间。

我们可以在当前版本复用未被修改地上一个版本的信息内存。

然而如何才能尽可能地去复用内存空间呢？这就需要树形结构了。

所以，对于所有的可持久化数据结构而言，都需要可持久化数组（一棵树）这样的基础。

怎么建立可持久化数组呢？可持久化数组的建立类似线段树，也就是可持久化线段树的建树过程。

所以说，可持久化线段树的建树是所有可持久化数据结构的学习基础。

可持久化并查集

并查集是一类用于判断图中两点是否连通的数据结构，其优点是时空复杂度低，但也有缺点，就是无法进行边的删除，只能进行边的添加。

如果我们要删除一些满足特定性质的边怎么办？比如删除最近添加的几条边？

显然最简单的并查集已经无法满足这个需求，所以我们借助可持久化数组将并查集升华成可持久化并查集。

并查集中有一个非常好的优化方法叫做路径压缩，但是如果在可持久化并查集中，这种优化方法就不适用了，因为它不能保持原来的各个连通块之间的关系，这样我们恢复历史版本的时候就会出问题。

为了使回溯历史版本时不出问题，再让并查集尽可能地优化，我们这里使用另外一种优化方法：按秩合并。

按秩合并的基本思路是：合并时将并查集树深度小的树根连到并查集树深度大的树根，以尽可能缩小并查集的深度。从而减少查找祖先的时间复杂度。

这种优化方法虽然没有路径压缩更优，但是非常契合可持久化的要求，所以拿来做可持久化并查集。

这里要注意，可持久化并查集中的可持久化数组的非叶子节点是没有意义的，只是拿来记录当前内存对应的原数组的下标区间，只有叶子节点才真正表示一个历史版本下某个节点的信息。

我们拆分成多个过程来看：

一、可持久化并查集的初始化建立

这一部分跟线段树差不多，只是到叶子节点的时候，其记录的信息要按照并查集按秩合并的初始化，将fa和dep全部初始化。

int build(int l,int r){
    int now = ++cnt;
    tr[now].l = l;
    tr[now].r = r;
    tr[now].lc = tr[now].rc = tr[now].fa = tr[now].dep = 0;
    if(l == r){
        tr[now].fa = l;
        tr[now].dep = 1;
        return now;
    }
    int mid = (l + r) >> 1;
    tr[now].lc = build(l,mid);
    tr[now].rc = build(mid+1,r);
    return now;
}

二、可持久化并查集的查询

无论我们对两点连通性做查询还是合并并查集，我们都离不开对点所属的并查集的根的查询。所以我们还是要做查询的。

在可持久化并查集中，我们每次查询都需要多一个查询的历史版本的参数。因为每个历史版本保存的信息并不一样，所以我们要先去找到当前历史版本下，我们要查询的这个点的在内存中到底在哪。

int query(int now,int pos){
    if(tr[now].l == tr[now].r)
        return now;
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)return query(tr[now].lc,pos);
    else return query(tr[now].rc,pos);
}

之后我们再类似按秩合并并查集的查询来进行根的查找。

int find(int rt,int pos){
    int now = query(rt,pos);
    if(tr[now].fa == pos)return now;
    return find(rt,tr[now].fa);
}

三、可持久化并查集的合并和深度更新

合并操作的时候，需要我们去创立一个新版本，这样才不会影响历史版本的信息。

然而新版本可以复用历史版本并未做修改的部分信息，只有需要修改的部分才需要新开辟内存。

int merge(int last,int pos,int fa){
    int now = ++cnt;
    tr[now] = tr[last];
    if(tr[now].l == tr[now].r){
        tr[now].fa = fa;
        tr[now].dep = tr[last].dep;
        return now;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)tr[now].lc = merge(tr[last].lc,pos,fa);
    else tr[now].rc = merge(tr[last].rc,pos,fa);
    return now;
}
void update(int now,int pos){
    if(tr[now].l == tr[now].r){
        tr[now].dep++;
        return;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)update(tr[now].lc,pos);
    else update(tr[now].rc,pos);
    return;
}

如果需要合并的两个并查集的深度不同，那么我们就把深度小的合到深度大的上。

如果深度相同，我们就需要将合并到的新的并查集的根深度+1。

四、历史版本

历史版本的根节点在内存中的下标位置保存在了root[x]中，直接从root[x]开始向下寻找即可。

总结代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct tree{
    int l,r,fa,lc,rc,dep;
}tr[maxn<<5];
int cnt = 0;
int root[maxn<<5];
int build(int l,int r){
    int now = ++cnt;
    tr[now].l = l;
    tr[now].r = r;
    tr[now].lc = tr[now].rc = tr[now].fa = tr[now].dep = 0;
    if(l == r){
        tr[now].fa = l;
        tr[now].dep = 1;
        return now;
    }
    int mid = (l + r) >> 1;
    tr[now].lc = build(l,mid);
    tr[now].rc = build(mid+1,r);
    return now;
}
int merge(int last,int pos,int fa){
    int now = ++cnt;
    tr[now] = tr[last];
    if(tr[now].l == tr[now].r){
        tr[now].fa = fa;
        tr[now].dep = tr[last].dep;
        return now;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)tr[now].lc = merge(tr[last].lc,pos,fa);
    else tr[now].rc = merge(tr[last].rc,pos,fa);
    return now;
}
void update(int now,int pos){
    if(tr[now].l == tr[now].r){
        tr[now].dep++;
        return;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)update(tr[now].lc,pos);
    else update(tr[now].rc,pos);
    return;
}
int query(int now,int pos){
    if(tr[now].l == tr[now].r)
        return now;
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)return query(tr[now].lc,pos);
    else return query(tr[now].rc,pos);
}
int find(int rt,int pos){
    int now = query(rt,pos);
    if(tr[now].fa == pos)return now;
    return find(rt,tr[now].fa);
}
void history(int now,int x){
    root[now] = root[x];
    return;
}
int opt;
int n,m;
int a,b;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    cnt = 0;
    root[0] = build(1,n);
    int nows = 0;
    while(m--){
        nows++;
        root[nows] = root[nows-1];
        cin >> opt;
        if(opt == 1){
            cin >> a >> b;
            int x = find(root[nows],a);
            int y = find(root[nows],b);
            if(tr[x].fa == tr[y].fa)continue;
            if(tr[x].dep > tr[y].dep)swap(x,y);
            root[nows] = merge(root[nows-1],tr[x].fa,tr[y].fa);
            if(tr[x].dep == tr[y].dep)update(root[nows],tr[y].fa);
        }
        else if(opt == 2){
            cin >> a;
            history(nows,a);
        }
        else{
            cin >> a >> b;
            int x = find(root[nows],a);
            int y = find(root[nows],b);
            if(tr[x].fa == tr[y].fa){
                cout << "1\n";
            }
            else cout << "0\n";
        }
    }
    return 0;
}

所以学习算法还是要举一反三啊QAQ

为什么要学这个？还不是因为博主ICPC2019南昌站的时候不会这个A题做不出来么……