可持久化并查集
并查集是很常见的数据结构，通常我们合并两颗子树之后就没法拆开了，但是如果我们能够访问历史版本的并查集，那么就可以达到拆开的效果了。
学习可持久化并查集需要先学习并查集和可持久化数组~
如何实现并查集的可持久化？
对于并查集来说，最重要的就是father[]数组了，所以我们主要维护的就是father[]数组的可持久化。
并查集优化
并查集有两种最常见的优化方式。分别是路径压缩和按秩合并。
路径压缩
路径压缩是最常见的并查集优化方式了，路径压缩的效果就是将一颗子树的一些非root结点连接到root结点上，从一颗瘦高的树变成一颗矮胖的树，从而减少查找时间。写法也非常的简单。
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
但是对于可持久化并查集来说，还能否使用路径压缩呢？答案是最好别了，因为对于可持久化的数据结构来说，每操作一次就要生成一个新的版本，存在MLE的风险。
按秩合并
按秩合并需要记录下每颗子树的树高，在合并两颗子树时，将矮的子树挂在高的子树上，那么新的子树的最坏查询时间不会增大，也是常见的优化方式。
按秩合并在可持久化并查集常用，也是有必要的。
可持久化并查集的实现
参数
// 维护可持久化数组的结点，因为要维护father数组和dep数组，所以开辟了80倍空间
struct node {
int l, r, val;
}tree[maxn * 40 * 2];
int rootfa[maxn], rootdep[maxn];
int cnt, tot;
可持久化数组
可持久化数组就没什么好说的，直接上板子
void build(int l, int r, int &now) {
now = ++cnt;
if (l == r) {
tree[now].val = ++tot; // tot达到fa[i] = i的效果
return;
}
int mid = (l + r) >> 1;
build(l, mid, tree[now].l);
build(mid+1, r, tree[now].r);
}
void modify(int l, int r, int pre, int &now, int pos, int val) {
now = ++cnt;
tree[now] = tree[pre];
if (l == r) {
tree[now].val = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) modify(l, mid, tree[pre].l, tree[now].l, pos, val);
else modify(mid+1, r, tree[pre].r, tree[now].r, pos, val);
}
int query(int l, int r, int now, int pos) {
if (l == r) return tree[now].val;
int mid = (l + r) >> 1;
if (pos <= mid) return query(l, mid, tree[now].l, pos);
else return query(mid+1, r, tree[now].r, pos);
}
并查集find()
find操作也非常的好写，注意不要路径压缩
// ver是版本号
int find(int ver, int x) {
int fx = query(1, n, rootfa[ver], x);
return fx == x ? x : find(ver, fx);
}
并查集merge()
merge操作使用按秩合并进行优化，需要注意的是，在合并时，当前版本是没有东西的，所以在操作时都要基于上一个版本。
void merge(int ver, int x, int y) {
x = find(ver-1, x); // 新版本还未操作，要从上一个版本找
y = find(ver-1, y);
if (x == y) {
rootfa[ver] = rootfa[ver-1];
rootdep[ver] = rootdep[ver-1];
} else {
int depx = query(1, n, rootdep[ver-1], x);
int depy = query(1, n, rootdep[ver-1], y);
if (depx < depy) {
modify(1, n, rootfa[ver-1], rootfa[ver], x, y);
rootdep[ver] = rootdep[ver-1];
} else if(depx > depy) {
modify(1, n, rootfa[ver-1], rootfa[ver], y, x);
rootdep[ver] = rootdep[ver-1];
} else {
modify(1, n, rootfa[ver-1], rootfa[ver], x, y);
modify(1, n, rootdep[ver-1], rootdep[ver], y, depy+1);
}
}
}
洛谷P3402
洛谷P3402是一道模板题
// 样例输入
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2
// 样例输出
1
0
1
// AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 2e5+5;
struct node {
int l, r, val;
}tree[maxn * 40 * 2];
int rootfa[maxn], rootdep[maxn];
int cnt, tot;
int n, m;
void build(int l, int r, int &now) {
now = ++cnt;
if (l == r) {
tree[now].val = ++tot;
return;
}
int mid = (l + r) >> 1;
build(l, mid, tree[now].l);
build(mid+1, r, tree[now].r);
}
void modify(int l, int r, int pre, int &now, int pos, int val) {
now = ++cnt;
tree[now] = tree[pre];
if (l == r) {
tree[now].val = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) modify(l, mid, tree[pre].l, tree[now].l, pos, val);
else modify(mid+1, r, tree[pre].r, tree[now].r, pos, val);
}
int query(int l, int r, int now, int pos) {
if (l == r) return tree[now].val;
int mid = (l + r) >> 1;
if (pos <= mid) return query(l, mid, tree[now].l, pos);
else return query(mid+1, r, tree[now].r, pos);
}
int find(int ver, int x) {
int fx = query(1, n, rootfa[ver], x);
return fx == x ? x : find(ver, fx);
}
void merge(int ver, int x, int y) {
x = find(ver-1, x); // 新版本还未操作，要从上一个版本找
y = find(ver-1, y);
if (x == y) {
rootfa[ver] = rootfa[ver-1];
rootdep[ver] = rootdep[ver-1];
} else {
int depx = query(1, n, rootdep[ver-1], x);
int depy = query(1, n, rootdep[ver-1], y);
if (depx < depy) {
modify(1, n, rootfa[ver-1], rootfa[ver], x, y);
rootdep[ver] = rootdep[ver-1];
} else if(depx > depy) {
modify(1, n, rootfa[ver-1], rootfa[ver], y, x);
rootdep[ver] = rootdep[ver-1];
} else {
modify(1, n, rootfa[ver-1], rootfa[ver], x, y);
modify(1, n, rootdep[ver-1], rootdep[ver], y, depy+1);
}
}
}
int main() {
scanf("%d%d", &n, &m);
build(1, n, rootfa[0]);
for (int i=1; i<=m; i++) {
int opt;
scanf("%d", &opt);
if (opt == 1) {
int a, b;
scanf("%d%d", &a, &b);
merge(i, a, b);
} else if(opt == 2) {
int k;
scanf("%d", &k);
rootfa[i] = rootfa[k];
rootdep[i] = rootdep[k];
} else {
int a, b;
scanf("%d%d", &a, &b);
rootfa[i] = rootfa[i-1];
rootdep[i] = rootdep[i-1];
int fa = find(i, a);
int fb = find(i, b);
printf("%d\n", (fa == fb ? 1 : 0));
}
}
return 0;
}