今天打算写一下 fhq-treap 启发式合并，然而发现看不懂自己的代码了...

# include <bits/stdc++.h>
# define rr register
const int N=100010;
struct Node{
	int son[2];
	int size;
	int val;
	int rnd;
}tree[N];
int cnt;
int f[N];
int n,m,q;
int root[N];
int val[N];
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline void NewNode(int &x,int v){
	x=++cnt;
	tree[x].rnd=rand();
	tree[x].size=1;
	tree[x].val=v;
	return;
}
inline int& lc(int x){
	return tree[x].son[0];
}
inline int& rc(int x){
	return tree[x].son[1];
}
inline void update(int x){
	tree[x].size=tree[lc(x)].size+tree[rc(x)].size+1;
	return;
}
void split(int now,int v,int &x,int &y){
	if(!now){
		x=y=0;
		return;
	}
	update(now);
	if(tree[now].val<=v){
		x=now;
		split(rc(now),v,rc(x),y);
		update(x);
	}else{
		y=now;
		split(lc(now),v,x,lc(y));
		update(y);
	}
	return;
}
void merge(int &now,int x,int y){
	if(!x||!y){
		now=x|y;
		return;
	}
	update(x),update(y);
	if(tree[x].rnd<tree[y].rnd){
		now=x;
		merge(rc(now),rc(x),y);
		update(now);
	}else{
		now=y;
		merge(lc(now),x,lc(y));
		update(now);
	}
	return;
}
inline int Insert(int &rt,int x,int v){
	int a,b;
	split(rt,v,a,b);
	merge(a,a,x);
	merge(rt,a,b);
	return rt;
}
int DeleteTree(int &now,int &nrt){
	if(!now)
		return 114514;
	DeleteTree(lc(now),nrt);
	DeleteTree(rc(now),nrt);
	lc(now)=rc(now)=0;
	return Insert(nrt,now,tree[now].val);
}
inline int FindRoot(int x){
	return root[x]==x?x:root[x]=FindRoot(root[x]);
}
inline int Kth(int x,int k){
	if(tree[x].size<k)
		return -1;
	while(1){
		if(k<=tree[lc(x)].size){
			x=lc(x);
		}else if(tree[lc(x)].size+1==k){
			return x;
		}else{
			k-=tree[lc(x)].size+1;
			x=rc(x);
		}
	}
	return 114514;
}
int main(void){
//	freopen("testdata.in","r",stdin);
//	freopen("testdata.out","w",stdout);
	srand(time(0));
	n=read(),m=read();
	for(rr int i=1;i<=n;++i){
		val[i]=read();
		NewNode(root[i],val[i]);
	}
	for(rr int i=1,x,y;i<=m;++i){
		x=read(),y=read();
		int rtx=FindRoot(x),rty=FindRoot(y);
		if(rtx==rty)
			continue;
		if(tree[rtx].size>tree[rty].size){
			std::swap(rtx,rty);
			std::swap(x,y);
		}
//		printf("qwq %d %d\n",rtx,rty); 这里
		root[rtx]=root[rty]=DeleteTree(rtx,rty);
//		printf("qwq %d\n",root[rtx]);
	}
	q=read();
	char opt;
	int x,y,k;
	while(q--){
		do{
			opt=getchar();
		}while(opt!='B'&&opt!='Q');
		if(opt=='B'){
			x=read(),y=read();
			int rtx=FindRoot(x),rty=FindRoot(y);
			if(rtx==rty)
				continue;
			if(tree[rtx].size>tree[rty].size){
				std::swap(rtx,rty);
				std::swap(x,y);
			}
//			printf("qwq %d %d\n",rtx,rty);			
			root[rtx]=root[rty]=DeleteTree(rtx,rty);	

//			printf("qwq %d\n",root[rtx]);
		}else{
			x=read(),k=read();
			printf("%d\n",Kth(FindRoot(x),k));
		}
	}
	return 0;
}

在合并完成之后，我并没有更新新根的祖先为它本身。

感觉正确的写法是：

		int s=DeleteTree(rtx,rty);
		root[rtx]=root[rty]=root[s]=s;

如果按照我的写法，似乎会出现下面的情况：

如果此时从红色节点进入并查集遍历，就死循环，挂掉了...

但是这份代码居然过了，，，所以是我脑抽看错了还是以前写挂了啊 qaq