WA72分求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6;
struct node {
	int ls,rs,sum,fa,id;
} tr[(N<<3)+1];
int cnt,a[N+1],m,n,b[N+1],rot[N+1],num,nxt[N+1],num2;
int build(int pl,int pr) {
	int rt=++cnt;
	if(pl==pr) {
		tr[rt].sum=1;
		tr[rt].fa=rt;
		tr[rt].id=pl;
		return rt;
	}
	int mid=(pl+pr)/2;
	tr[rt].ls=build(pl,mid);
	tr[rt].rs=build(mid+1,pr);
	return rt;
}
int query(int p,int pl,int pr,int x) {
	if(pl==pr)return p;
	int mid=(pl+pr)/2;
	if(x<=mid)return query(tr[p].ls,pl,mid,x);
	return query(tr[p].rs,mid+1,pr,x);
}
int updatefa(int last,int pl,int pr,int son,int fa) {
	++cnt;
	int p=cnt;
	tr[cnt]=tr[last];
	if(pl==pr) {
		tr[cnt].fa=fa;
		return p;
	}
	int mid=(pl+pr)/2;
	if(son<=mid)tr[p].ls=updatefa(tr[last].ls,pl,mid,son,fa);
	else tr[p].rs=updatefa(tr[last].rs,mid+1,pr,son,fa);
	return p;
}
int updatesum(int last,int pl,int pr,int x,int d) {
	//cout<<pl<<" "<<pr<<"\n";
	++cnt;
	int p=cnt;
	tr[cnt]=tr[last];
	if(pl==pr) {
		tr[cnt].sum+=d;
		return p;
	}
	int mid=(pl+pr)/2;
	if(x<=mid)tr[p].ls=updatesum(tr[last].ls,pl,mid,x,d);
	else tr[p].rs=updatesum(tr[last].rs,mid+1,pr,x,d);
	return p;
}
int find(int p) {
	if(tr[tr[p].fa].id==tr[p].id)return p;
	return find(tr[p].fa);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	rot[0]=build(1,n);
	for(int i=1; i<=m; i++) {
		int k,op,x,y;
		cin>>op;
		if(op==1) {
			cin>>x>>y;
			x=query(rot[num],1,n,x);
			x=find(x);
			y=query(rot[num],1,n,y);
			y=find(y);
			if(x==y) {
				cnt++;
				rot[num+1]=cnt;
				num++;
				nxt[i]=num;
				tr[cnt]=tr[rot[num-1]];
				continue;
			}
			if(tr[x].sum<tr[y].sum)swap(x,y);
			rot[num+1]=updatefa(rot[num],1,n,tr[y].id,x);
			num++;
			rot[num+1]=updatesum(rot[num],1,n,tr[x].id,tr[y].sum);
			num++;
			nxt[i]=num;
		}
		if(op==2) {
			cin>>k; 
			num++;
			cnt++;
			rot[num]=cnt;
			tr[cnt]=tr[rot[nxt[k]]];
			nxt[i]=num;
		}
		if(op==3) {
			cin>>x>>y;
			x=query(rot[num],1,n,x);
			x=find(x);
			y=query(rot[num],1,n,y);
			y=find(y);
		//	cout<<x<<" "<<y<<"\n";
			if(tr[x].id==tr[y].id)cout<<1<<"\n";
			else cout<<0<<"\n";
			num++;
			nxt[i]=num;
			++cnt;
			rot[num]=cnt;
			tr[cnt]=tr[rot[num-1]];
		}
	}
	return 0;
}
/*
5 2
1 1 2
3 1 2 
*/