可持久化并查集

因为这个版本感觉特别清楚就写个博客保留一下（
可持久化数组，都说是个数组了，那很多用数组维护的东西就都可以可持久化了。可持久化并查集，其实就是用主席树代替了原来的 \(fa\) 数组和 \(dep\) 数组，别的都是并查集的操作。注意不能写路径压缩，只能按秩合并，因为一旦路径压缩就可能会涉及到多个修改，复杂度就没有保证了（每次修改都得新开版本）。

模板代码，注释很详细。

//可！持！久！化！并！查！集！
//只要是树就都可以持久化是吧（ 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
struct node
{
	int l, r, val; 
}tr[N*40*2];//这里相当于用一棵主席树干了两个树的活（只要把root存对问题都不大 
int idx, tot, rootfa[N], rootdep[N];//idx用来开点，tot用来赋值（初始fa）（啊好像没啥用，而且不太稳定。。。）
//tot这里有点多余w 
int n, m;

void build(int l, int r, int &u)
{
	u = ++idx;//开点 
	if(l==r) return tr[u].val = l, void();//相当于fa[i] = i; 
	int mid = (l+r)>>1;
	build(l, mid, tr[u].l);
	build(mid+1, r, tr[u].r);
}
//建树操作，因为fa要初始化，当然dep并不用
void modify(int l, int r, int ver, int &u, int pos, int val)//修改操作，相当于单点赋值 
{
	u = ++idx;
	tr[u] = tr[ver];//复制上一个版本，只对有修改的地方进行修改 ； 
	if(l == r) return tr[u].val = val, void();//递归到底，赋值； 
	int mid = (l+r)>>1;
	if(pos<=mid) modify(l, mid, tr[ver].l, tr[u].l, pos, val);
	else modify(mid+1, r, tr[ver].r, tr[u].r, pos, val);
}
int query(int l, int r, int u, int pos)
{
	if(l == r) return tr[u].val;//递归到底，取值，相当于取某个数组某下标对应的值 
	int mid = (l+r)>>1;
	if(pos<=mid) return query(l, mid, tr[u].l, pos);
	else return query(mid+1, r, tr[u].r, pos);
}
int find(int ver, int x)
{
	int fx = query(1, n, rootfa[ver], x);
	if(x!=fx) x = find(ver, fx);
	return x;
}

void merge(int ver, int x, int y)
{
	x = find(ver-1, x);//注意，这里的版本ver是更新后的版本 
	y = find(ver-1, y);//故应去版本ver中寻找 
	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]);//初始化fa“数组” 
	for(int i = 1; i<=m; i++)
	{
		int op, a, b;
		scanf("%d", &op);
		if(op == 1)
		{
			scanf("%d%d", &a, &b);
			merge(i, a, b);
			
		}
		else if(op == 2)
		{
			int k;
			scanf("%d", &k);
			rootfa[i] = rootfa[k];
			rootdep[i] = rootdep[k];
		}
		else
		{
			scanf("%d%d", &a, &b);
			rootfa[i] = rootfa[i-1];
			rootdep[i] = rootdep[i-1];
			a = find(i, a);
			b = find(i, b);
			if(a == b) puts("1");
			else puts("0");
		}
	}
	return 0;
}
//总结：就是并查集，就是并查集，就是并查集……
/*
操作一模一样，只是用主席树维护数组
将赋值操作变得有亿点点点麻烦
线段树来存储每个节点的父节点 
*/