记录编号	440940	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.004 s
提交时间	2017-08-24 11:21:34	内存使用	1.07 MiB

#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=1e5+10;
struct Treap{
	Treap *lc,*rc;
	int val,size,ran,id;
	Treap(int key,int ID){
		lc=rc=0;size=1;ran=rand();
		val=key;id=ID;
	}
	~Treap(){delete lc;delete rc;}
}*root[N];
int size(Treap *x){return x?x->size:0;}
void update(Treap *x){
	x->size=size(x->lc)+size(x->rc)+1;
}
Treap *merge(Treap *x,Treap *y){
	if (!x) return y;
	if (!y) return x;
	if (x->ran>y->ran){
		x->rc=merge(x->rc,y);
		update(x);
		return x;
	}
	else{
		y->lc=merge(x,y->lc);
		update(y);
		return y;
	}
}
int find(Treap *x,int rank){
	if (rank>x->size) return -1;
	int i=size(x->lc)+1;
	if (i==rank) return x->id;
	return i<rank?find(x->rc,rank-i):find(x->lc,rank);
}
void split(Treap *x,Treap *&lt,Treap *&rt,int key){
	if (!x) return void(lt=rt=0);
	if (x->val<=key){
		split(x->rc,lt,rt,key);
		x->rc=lt;update(lt=x);
	}
	else{
		split(x->lc,lt,rt,key);
		x->lc=rt;update(rt=x);
	}
}
Treap *Merge(Treap *x,Treap *y){
	if (!x) return y;
	if (!y) return x;
	if (x->ran<y->ran) swap(x,y);
	Treap *lx=x->lc,*rx=x->rc,*ly,*ry;
	x->lc=x->rc=0;x->size=1;
	split(y,ly,ry,x->val);
	x->lc=Merge(lx,ly);
	x->rc=Merge(rx,ry);
	update(x);
	return x;
}
int n,m,q,fa[N],x,y;
char s[10];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main()
{
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	srand((unsigned)time(0));
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		fa[i]=i;
		scanf("%d",&x);
		root[i]=new Treap(x,i);
	}
	for (int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		x=find(x);y=find(y);
		if (x!=y) root[x]=Merge(root[x],root[y]),fa[y]=x;
	}
	scanf("%d",&q);
	while (q--){
		scanf("%s%d%d",s,&x,&y);
		if (s[0]=='Q')
			printf("%d\n",find(root[find(x)],y));
		else{
			x=find(x);y=find(y);
			if (x!=y) root[x]=Merge(root[x],root[y]),fa[y]=x;
		}
	}
	return 0;
}