rt.稳定TLE on #11 #14用时稳定约2s

本机O2稳过

#include<bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
struct sgm_t{
	int nw,ls,rs,val;
}a[N<<5];
int n,m,op,aa,bb,arr[N],root[N],sz;
void pushup(int nw){a[nw].val=a[a[nw].ls].val+a[a[nw].rs].val;}
void bui(int nw,int l,int r){
	a[nw].ls=(nw<<1);a[nw].rs=(nw<<1)+1;
	sz=max(sz,nw);
	if(l==r)
		a[nw].val=arr[l];
	else{
		bui((nw<<1),l,(l+r)>>1);
		bui((nw<<1)+1,1+((l+r)>>1),r);
		pushup(nw);
	}
}
int fix(int nw,int pos,int v,int l,int r){
	a[++sz]=a[nw];
	int ret=sz;
	if(l==r)
		a[ret].val=v;
	else if(pos>(l+r)>>1)
		a[ret].rs=fix(a[nw].rs,pos,v,1+((l+r)>>1),r);
	else a[ret].ls=fix(a[nw].ls,pos,v,l,(l+r)>>1);
	return ret;
}
int wha(int nw,int pos,int l,int r){
	if(l==r)
		return a[nw].val;
	else if(pos>(l+r)>>1)
		return wha(a[nw].rs,pos,1+((l+r)>>1),r);
	return wha(a[nw].ls,pos,l,(l+r)>>1);
}
int findfa(int a,int ver){
	int t=wha(root[ver],a,1,n);
	if(t==a)return a;
	else{
		t=findfa(t,ver);
		return t;
	}
}
int mrg(int a,int b,int ver){
	if(rand()%2)
		return fix(root[ver],findfa(min(a,b),ver),findfa(max(a,b),ver),1,n);
	return fix(root[ver],findfa(max(a,b),ver),findfa(min(a,b),ver),1,n);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie();cout.tie();
	srand(time(NULL));
	cin>>n>>m;
	for(int i=1;i<=n;i++)arr[i]=i;
	n=1<<(int)(1e-6+ceil(1e-6+log(n)/log(2)));
	bui(1,1,n);root[0]=1;
	for(int i=1;i<=m;i++){
		cin>>op>>aa;
		if(op==1){
			cin>>bb;root[i]=mrg(aa,bb,i-1);
		}
		else if(op==2)
			a[root[i]=++sz]=a[root[aa]];
		else{
			a[root[i]=++sz]=a[root[i-1]];
			cin>>bb;
			cout<<(findfa(aa,i-1)==findfa(bb,i-1))<<endl; 
		}
	}
	return 0;
}