可持久化数据结构
众所周知,在竞赛界有这么一种神奇的解决方案,用以解决简单数据结构无法恢复历史版本的问题。
它就是可持久化!
如何可持久化?当然是要记录历史信息了。
但是那消耗空间不会巨大吗?
起始如果我们可以合理运用历史版本信息,我们就可以在创建新版本的时候尽可能地缩减需要的空间。
我们可以在当前版本复用未被修改地上一个版本的信息内存。
然而如何才能尽可能地去复用内存空间呢?这就需要树形结构了。
所以,对于所有的可持久化数据结构而言,都需要可持久化数组(一棵树)这样的基础。
怎么建立可持久化数组呢?可持久化数组的建立类似线段树,也就是可持久化线段树的建树过程。
所以说,可持久化线段树的建树是所有可持久化数据结构的学习基础。
可持久化并查集
并查集是一类用于判断图中两点是否连通的数据结构,其优点是时空复杂度低,但也有缺点,就是无法进行边的删除,只能进行边的添加。
如果我们要删除一些满足特定性质的边怎么办?比如删除最近添加的几条边?
显然最简单的并查集已经无法满足这个需求,所以我们借助可持久化数组将并查集升华成可持久化并查集。
并查集中有一个非常好的优化方法叫做路径压缩,但是如果在可持久化并查集中,这种优化方法就不适用了,因为它不能保持原来的各个连通块之间的关系,这样我们恢复历史版本的时候就会出问题。
为了使回溯历史版本时不出问题,再让并查集尽可能地优化,我们这里使用另外一种优化方法:按秩合并。
按秩合并的基本思路是:合并时将并查集树深度小的树根连到并查集树深度大的树根,以尽可能缩小并查集的深度。从而减少查找祖先的时间复杂度。
这种优化方法虽然没有路径压缩更优,但是非常契合可持久化的要求,所以拿来做可持久化并查集。
这里要注意,可持久化并查集中的可持久化数组的非叶子节点是没有意义的,只是拿来记录当前内存对应的原数组的下标区间,只有叶子节点才真正表示一个历史版本下某个节点的信息。
我们拆分成多个过程来看:
一、可持久化并查集的初始化建立
这一部分跟线段树差不多,只是到叶子节点的时候,其记录的信息要按照并查集按秩合并的初始化,将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题做不出来么……
没有帐号? 立即注册