可持久化dsu 92pts求调www

#include<bits/stdc++.h>
using namespace std;
struct pers_dsu
{
	int n; //并查集的大小 
	struct pers_array
	{
		struct node
		{
			int lson , rson;
			int val;
		};
		static const int MAXN = 1e5 + 10;
		int cnt , rtpos[MAXN]; //cnt存储节点数量，rtpos存储每个版本的根节点 
		node k[MAXN << 5]; //k存储树上节点的信息
		void build(int &rt , int l , int r , bool op) //建树，只有叶子节点存储信息，op=0表示该可持久化数组用于存储fa，op=1表示该可持久化数组用于存储dep
		{
			rt = ++cnt , k[rt].val = 0;
			int mid = (l + r) >> 1;
			if(l == r)
			{
				if(!op) k[rt].val = mid;
				else k[rt].val = 1;
				return;
			}
			build(k[rt].lson , l , mid , op);
			build(k[rt].rson , mid + 1 , r , op);
			return;
		}
		int modify(int rt , int l , int r , int pos , int kval) //将pos节点的值修改为kval，函数的返回值为当前新修改的节点的编号
		{
			int neort = ++cnt , mid = (l + r) >> 1;
			if(l == r)
			{
				k[neort].val = kval;
				return neort;
			}
			k[neort] = k[rt];
			if(pos <= mid) k[neort].lson = modify(k[rt].lson , l , mid , pos , kval);
			if(pos >= mid + 1) k[neort].rson = modify(k[rt].rson , mid + 1 , r , pos , kval);
			return neort;
		}
		int query(int rt , int l , int r , int pos) //询问pos位置上的值，如果要求询问后的数组也作为一个新版本，我们不用显式地按题意建一个版本，只需让两个版本rtpos相等即可
		{
			int mid = (l + r) >> 1;
			if(l == r) return k[rt].val;
			if(pos <= mid) return query(k[rt].lson , l , mid , pos);
			if(pos >= mid + 1) return query(k[rt].rson , mid + 1 , r , pos);
		}
	};
	pers_array fa , sz; //fa数组和sz数组，注意并查集必须采用按秩合并的方式，这里把集合大小作为秩 
	void init(int x) //初始化并查集
	{
		n = x;
		fa.build(fa.rtpos[0] , 1 , n , 0);
		sz.build(sz.rtpos[0] , 1 , n , 1);
		return;
	}
	int find(int id , int x) //在id版本查询x的fa值 
	{
		int fapos = fa.query(fa.rtpos[id] , 1 , n , x);
		if(x == fapos) return x;
		return find(id , fapos);
	}
	void merge(int id , int x , int y) //合并id版本的集合x与集合y
	{
		int fx = find(id , x) , fy = find(id , y);
		if(fx == fy) return;
		int szx = sz.query(sz.rtpos[id] , 1 , n , fx) , szy = sz.query(sz.rtpos[id] , 1 , n , fy);
		if(szx <= szy)
		{
			fa.rtpos[id] = fa.modify(fa.rtpos[id] , 1 , n , fx , fy);
			sz.rtpos[id] = sz.modify(sz.rtpos[id] , 1 , n , fy , szx + szy);
		}
		else
		{
			fa.rtpos[id] = fa.modify(fa.rtpos[id] , 1 , n , fy , fx);
			sz.rtpos[id] = sz.modify(sz.rtpos[id] , 1 , n , fx , szx + szy);
		}
		return;
	}
};
pers_dsu T;
int n , m; 
int main()
{
	cin >> n >> m;
	T.init(n);
	for(int i = 1 ; i <= m ; i++)
	{
		int op;
		scanf("%d" , &op);
		T.fa.rtpos[i] = T.fa.rtpos[i - 1];
		T.sz.rtpos[i] = T.sz.rtpos[i - 1];
		if(op == 1)
		{
			int a , b;
			scanf("%d%d" , &a , &b);
			T.merge(i , a , b);
		}
		if(op == 2)
		{
			int x;
			scanf("%d" , &x);
			T.fa.rtpos[i] = T.fa.rtpos[x];
			T.sz.rtpos[i] = T.sz.rtpos[x];
		}
		if(op == 3)
		{
			int a , b;
			scanf("%d%d" , &a , &b);
			if(T.find(i , a) == T.find(i , b)) printf("1\n");
			else printf("0\n");
		}
	}
	return 0;
}