只需要随便yy一下主席数就可以咯

两题用同一个代码就可以啦

# include <stdio.h>
# include <algorithm>
using namespace std;
int n,m,cnt=0;
const int M=12000010;
int root[M],ch[M][2],s[M],d[M];
void build(int &rt,int l,int r) {
	if(!rt) rt=++cnt;
	if(l==r) {s[rt]=l;return;}
	int mid=l+r>>1;
	build(ch[rt][0],l,mid);
	build(ch[rt][1],mid+1,r);
}
void modify(int l,int r,int oldrt,int &rt,int pos,int val) {
	rt=++cnt;
	if(l==r) {
		s[rt]=val;
		d[rt]=d[oldrt];
		return ;
	}
	ch[rt][0]=ch[oldrt][0],ch[rt][1]=ch[oldrt][1];
	int mid=l+r>>1;
	if(pos<=mid) modify(l,mid,ch[oldrt][0],ch[rt][0],pos,val);
	else modify(mid+1,r,ch[oldrt][1],ch[rt][1],pos,val);
}

int query(int rt,int l,int r,int pos) {
	if(l==r) return rt;
	int mid=l+r>>1;
	if(pos<=mid) return query(ch[rt][0],l,mid,pos);
	else return query(ch[rt][1],mid+1,r,pos);
}

void add(int rt,int l,int r,int pos) {
	if(l==r) {
		d[rt]++;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) add(ch[rt][0],l,mid,pos);
	else add(ch[rt][1],mid+1,r,pos);
}

int get(int rt,int x) {
	int rtt=query(rt,1,n,x);
	if(x==s[rtt]) return rtt;
	return get(rt,s[rtt]);
}

int main() {
	scanf("%d%d",&n,&m);
	build(root[0],1,n);
	for (int i=1;i<=m;++i) {
		int buf,a,b,k;
		scanf("%d",&buf);
		if(buf==1) {
			root[i]=root[i-1];
			scanf("%d%d",&a,&b);
			int p=get(root[i],a),q=get(root[i],b);
			if(s[p]==s[q]) continue;
			if(d[p]>d[q]) swap(p,q);
			modify(1,n,root[i-1],root[i],s[p],s[q]);
			if(d[p]==d[q]) add(root[i],1,n,s[q]);
		} else if(buf==2) {
			scanf("%d",&k);
			root[i]=root[k];
		} else if(buf==3) {
			root[i]=root[i-1];
			scanf("%d%d",&a,&b);
			int p=get(root[i],a),q=get(root[i],b);
			if(s[p]==s[q]) puts("1");
			else puts("0");
		}
	}
}