rt

不知道是按秩合并挂了还是人傻常数大。。。照着题解改了改也没用

// luogu.P3402 可持久化并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20],*p1=buf,*p2=buf;
template<typename T>void read(T &x){
	x=0;int f=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10-48+c;
	x*=f;
}

int n,m;

int ind,rt[N],ls[N*30],rs[N*30],fa[N*30],dep[N*30];

#define mid (l+r>>1)
void build(int &u,int l,int r) {
	u = ++ind;
	if( l == r ) { fa[u] = l; return; }
	build(ls[u],l,mid), build(rs[u],mid+1,r);
}
void merge(int lst,int &u,int l,int r,int pos,int f) {
	u = ++ind, ls[u] = ls[lst], rs[u] = rs[lst];
	if( l == r ) {
		fa[u] = f, dep[u] = dep[lst];
		return;
	}
	if( pos <= mid ) merge(ls[lst],ls[u],l,mid,pos,f);
	else merge(rs[lst],rs[u],mid+1,r,pos,f);
}
void up(int u,int l,int r,int pos) {
	if( l == r ) { ++dep[u]; return; }
	if( pos <= mid ) up(ls[u],l,mid,pos);
	else up(rs[u],mid+1,r,pos);
}
int query(int u,int l,int r,int pos) {
	if( l == r ) return u;
	if( pos <= mid ) return query(ls[u],l,mid,pos);
	else return query(rs[u],mid+1,r,pos);
}
int find(int root,int pos) {
	int now = query(root,1,n,pos);
	return fa[now]==pos ? now : find(root,fa[now]);
}

int main() {
	read(n),read(m);
	build(rt[0],1,n);
	for(int i = 1; i <= m; ++i) {
		int op,x,y; read(op),read(x);
		if( op == 1 ) {
			read(y);
			rt[i] = rt[i-1];
			int fax = find(rt[i],x), fay = find(rt[i],y);
			if( fa[fax] != fa[fay] ) {
				if( dep[fax] > dep[fay] ) swap(x,y);
				merge(rt[i-1],rt[i],1,n,fa[fax],fa[fay]);
				if( dep[fax] == dep[fay] ) up(rt[i],1,n,fa[fay]);
			}
		} else if( op == 2 ) rt[i] = rt[x];
		else {
			read(y);
			rt[i] = rt[i-1];
			puts(find(rt[i],x)==find(rt[i],y) ? "1" : "0");
		}
	}
	return 0;
}