记录编号	152142	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	1.040 s
提交时间	2015-03-13 11:44:33	内存使用	24.35 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>

typedef class Node* node;

using namespace std;

struct Node{
	Node* ch[2];
	int sum,r,v,pos;
	void update(){
		sum=ch[0]->sum+ch[1]->sum+1;
	}
	int cmp(int x){return x>v;}
	node init(int x,int t);
}Null={0},spT[1000010],*root[100010];

int n,m,tot_spT=0,father[100010],siz[100010];

node Node::init(int x,int t){
	sum=1; v=x; pos=t;
	ch[0]=ch[1]=&Null; r=rand();
	return this;
}

void rot(node &o,int x){
	node tmp=o->ch[x];
	o->ch[x]=tmp->ch[x^1];
	tmp->ch[x^1]=o;
	o->update(); o=tmp;
	o->update();
}

void insert(node &o,int x,int pos){
	if(o==&Null) o=spT[++tot_spT].init(x,pos);
	else{
		int t=o->cmp(x);
		insert(o->ch[t],x,pos);
		if(o->ch[t]->r > o->r) rot(o,t);
		o->update();
	}
}

int kth(node o,int k){
	if(o==&Null||k>o->sum||!k) return -1;
	if(k>o->ch[0]->sum){
		int tmp=o->ch[0]->sum+1;
		if(k<=tmp) return o->pos;
		else return kth(o->ch[1],k-tmp);
	}
	return kth(o->ch[0],k);
}

int find(int x){
	if(father[x]!=x) father[x]=find(father[x]);
	return father[x];
}

void mergeto(node &from,node &to){
	if(from==&Null) return;
	if(from->ch[0]!=&Null) mergeto(from->ch[0],to);
	if(from->ch[1]!=&Null) mergeto(from->ch[1],to);
	if(from!=&Null){
		insert(to,from->v,from->pos);
		from=&Null;
	}
}

void unionn(int x,int y){
	int r1=find(x),r2=find(y);
	if(r1!=r2){
		if(siz[r1]>siz[r2]) swap(r1,r2);
		siz[r2]+=siz[r1];
		father[r1]=r2;
		mergeto(root[r1],root[r2]);
		root[r1]=&Null; siz[r1]=0;
	}
}

int main(){
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	srand(time(NULL));
	scanf("%d%d",&n,&m);
	int u,v,q;
	char ch;
	for(int i=1;i<=n;i++)
		siz[i]=1,root[i]=&Null,father[i]=i;
	for(int i=1;i<=n;i++){
		scanf("%d",&u);
		insert(root[i],u,i);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		unionn(u,v);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		while(ch=getchar(),ch<='!');
		scanf("%d%d",&u,&v);
		if(ch=='B') unionn(u,v);
		else printf("%d\n",kth(root[find(u)],v));
	}
	return 0;
}