记录编号	156138	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.782 s
提交时间	2015-04-02 18:47:37	内存使用	15.76 MiB

#include<cstdio>
#include<cstdlib>
const int maxn=100010;
char ch[10000000],co[5000000],*ptr=ch,*po=co;
struct node{
	node *c[2];
	int v,r,b,siz;
	void init(int x,int y);
	node(){v=r=b=siz=0,c[0]=c[1]=NULL;}
	void update(){siz=c[0]->siz+c[1]->siz+1;}
};
node *Null=new node,*root[maxn];
void node::init(int x,int y){
	v=x,b=y,r=rand(),siz=1;
	c[0]=c[1]=Null;
}
void out(int x){
	static int f=0;
	static char p[10];
	while(x) p[++f]=x%10+'0',x/=10;
	while(f) *po++=p[f--];
	*po++='\n';
}
void rot(node *&o,int d){
	node *tmp=o->c[!d];
	o->c[!d]=tmp->c[d],tmp->c[d]=o;
	o->update(),tmp->update(),o=tmp;
}
void ins(node *&o,int x,int y){
	if(o==Null) {o=new node,o->init(x,y);return;}
	int d;if(x<o->v) d=0;else d=1;
	ins(o->c[d],x,y);
	if(o->c[d]->r<o->r) rot(o,!d);
	o->update();
}
void kth(node *root,int k){
	int now;
	node *o=root;
	while(o!=Null){
		now=o->c[0]->siz+1;
		if(now==k) {out(o->b);return;}
		else if(now>k) o=o->c[0];
		else k-=now,o=o->c[1]; 
	}
	*po++='-',*po++='1',*po++='\n';
}
int n,m,fa[maxn],siz[maxn];
int findfa(int x){
	if(fa[x]==x) return x;
	return fa[x]=findfa(fa[x]);
}
void in(int &x){
	x=0;
	while(*ptr<48) ptr++;
	while(*ptr>47) x=x*10+*ptr++-48;
}
void link(node *p,node *&o){
	if(p==Null) return;
	ins(o,p->v,p->b),link(p->c[0],o),link(p->c[1],o);
}
void Union(int x,int y){
	x=findfa(x),y=findfa(y);
	if(x==y) return;
	if(siz[x]>siz[y]) fa[y]=x,siz[x]+=siz[y],link(root[y],root[x]),root[y]=Null;
	else fa[x]=y,siz[y]+=siz[x],link(root[x],root[y]),root[x]=Null;
}
int main(){
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	fread(ch,1,10000000,stdin);
	in(n),in(m);
	for(int a,i=1;i<=n;i++) in(a),fa[i]=i,root[i]=Null,ins(root[i],a,i),siz[i]=1;
	for(int x,y,i=1;i<=m;i++) in(x),in(y),Union(x,y);
	in(m);int x,y,z;
	while(m--){
		while(*ptr<60) ptr++;
		if(*ptr=='B') ptr++,in(x),in(y),Union(x,y);
		else ptr++,in(x),in(y),kth(root[findfa(x)],y);
	}
	fwrite(co,1,po-co,stdout);
}