P3402 persistent and searchable

Topic link ： Click here

The main idea of the topic ：
Given $n$ A collection of , The first $i$ There is only one number in the initial state in a set , by $i$.

Yes $m$ operations . The operation is divided into $3$ Kind of ：

$1ab$ Merge $a,b$ In the collection ;

$2k$ Back to the first $k$ operations （ Performing any of the three operations is recorded as an operation ） The state after ;

$3ab$ inquiry $a,b$ Whether they belong to the same set , Output if yes $1$ , Otherwise output $0$.
For each operation $3$, Output an integer on a line to represent the answer

Topic analysis ：
Use the chairman tree to build a persistent array to serve as the array subscript of the original union search set , For the search operation that the search subscript directly corresponds to the persistent array
The idea of rank based merging is needed to perform the merging operation to ensure the time complexity , The reason for not using path compression is that using path compression may make it easy for updates to generate a lot of redundant space $MLE$

See code for details ：

// Problem: P3402  Persistent and searchable 
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3402
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<unordered_map>
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
//#define int ll
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
int read()
{
    
	int res = 0,flag = 1;
	char ch = getchar();
	while(ch<'0' || ch>'9')
	{
    
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9')
	{
    
		res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
		ch = getchar();
	}
	return res*flag;
}
const int maxn = 1e6+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
struct node{
    
	int l,r;
}nod[maxn*32];
int n,m,cnt,root[maxn],fa[maxn*32],dep[maxn*32];
void build(int &u,int l,int r)
{
    
	nod[u = ++cnt];
	if(l == r)
	{
    
		fa[u] = l;
		return ;
	}
	int mid = l+r>>1;
	build(nod[u].l,l,mid);
	build(nod[u].r,mid+1,r);
}
int query(int u,int l,int r,int pos)
{
    
	if(l == r) return u;
	int mid = l+r>>1;
	if(pos <= mid) return query(nod[u].l,l,mid,pos);
	else return query(nod[u].r,mid+1,r,pos);
}
int find(int root,int x)
{
    
	int pos = query(root,1,n,x);
	if(fa[pos] == x) return pos;
	return find(root,fa[pos]);
}
void update(int &u,int pre,int l,int r,int pos,int fax) //  modify pos My father is fax
{
    
	nod[u = ++cnt];
	if(l == r)
	{
    
		fa[u] = fax;
		dep[u] = dep[pre];
		return ;
	}
	int mid = l+r>>1;
	nod[u].l = nod[pre].l;
	nod[u].r = nod[pre].r;
	if(pos <= mid) update(nod[u].l,nod[pre].l,l,mid,pos,fax);
	else update(nod[u].r,nod[pre].r,mid+1,r,pos,fax);
}
void add(int u,int l,int r,int pos) //  Add one to the root depth of a union search set 
{
    
	if(l == r)
	{
    
		dep[u]++;
		return ;
	}
	int mid = l+r>>1;
	if(pos <= mid) add(nod[u].l,l,mid,pos);
	else add(nod[u].r,mid+1,r,pos);
}
int main()
{
    
	n = read(),m = read();
	build(root[0],1,n);
	for(int i = 1;i <= m;i++)
	{
    
		int opt = read();
		if(opt == 1)
		{
    
			int x = read(),y = read();
			root[i] = root[i-1];
			int px = find(root[i],x),py = find(root[i],y);
			if(fa[px] == fa[py]) continue;
			if(dep[px] > dep[py]) swap(px,py);
			update(root[i],root[i-1],1,n,fa[px],fa[py]);
			if(dep[px] == dep[py]) add(root[i],1,n,fa[py]); //  Note that fa[py], Because the new root at this time is fa[py], The depth is increased 1
		}
		else if(opt == 2)
		{
    
			int id = read();
			root[i] = root[id];
		}
		else if(opt == 3)
		{
    
			int x = read(),y = read();
			root[i] = root[i-1];
			int fax = find(root[i],x),fay = find(root[i],y);
			puts(fax==fay ? "1" : "0");
		}
	}
	return 0;
}