记录编号	358969	评测结果	WWWWWWWWWW
题目名称	[HNOI 2012] 永无乡	最终得分	0
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.863 s
提交时间	2016-12-20 07:35:52	内存使用	62.86 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define siz(x) ((x)?(x)->size:0)
using namespace std;
const int maxn=100010;
struct node{
	static int randint(){
		static int a=1213,b=198897,c=975481241,x=18448783,p=998244353;
		x=a*x*x+b*x+c;x%=p;
		return x<0?(x=-x):x;
	}
	int data,size,p;
	node *ch[2];
	inline void refresh(){size=siz(ch[0])+siz(ch[1]);}
	inline int cmp(int x){return x==data?-1:x>data;}
}nodes[maxn<<5],*ptr=nodes,*root[maxn]={NULL};
int findroot(int);
void mergeset(int,int);
void merge(node*&,node*);
void insert(int,node*&);
node *kth(int,node*);
void rot(node*&,int);
int n,m,a[maxn],p[maxn],prt[maxn],x,y;
char c;
node *z;
int main(){
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
		prt[i]=i;
		a[p[i]]=i;
		insert(p[i],root[i]);
	}
	while(m--){
		scanf("%d%d",&x,&y);
		mergeset(x,y);
	}
	scanf("%d",&m);
	while(m--){
		scanf(" %c %d%d",&c,&x,&y);
		if(c=='Q'){
			if((z=kth(y,root[x=findroot(x)])))printf("%d\n",a[z->data]);
			else printf("-1\n");
		}
		else if(c=='B')mergeset(x,y);
	}
	return 0;
}
int findroot(int x){
	int rt=prt[x],y;
	while(prt[rt]!=rt)rt=prt[rt];
	while(prt[x]!=rt){
		y=prt[x];
		prt[x]=rt;
		x=y;
	}
	return rt;
}
void mergeset(int x,int y){
	x=findroot(x);y=findroot(y);
	if(x==y)return;
	if(siz(root[x])<siz(root[y]))swap(x,y);
	prt[y]=x;
	merge(root[x],root[y]);
}
void merge(node *&x,node *y){
	if(!y)return;
	merge(x,y->ch[0]);
	insert(y->data,x);
	merge(x,y->ch[1]);
}
void insert(int x,node *&rt){
	if(!rt){
		rt=ptr++;
		rt->data=x;
		rt->size=1;
		rt->p=node::randint();
		rt->ch[0]=rt->ch[1]=NULL;
		return;
	}
	int d=rt->cmp(x);
	insert(x,rt->ch[d]);
	rt->refresh();
	if(rt->ch[d]->p<rt->p)rot(rt,d^1);
}
node *kth(int k,node *rt){
	int d;
	while(rt){
		if(k==siz(rt->ch[0])+1)return rt;
		if((d=k>siz(rt->ch[0])))k-=siz(rt->ch[0])+1;
		rt=rt->ch[d];
	}
	return NULL;
}
void rot(node *&x,int d){
	node *y=x->ch[d^1];
	x->ch[d^1]=y->ch[d];
	y->ch[d]=x;
	x->refresh();
	(x=y)->refresh();
}