记录编号	152776	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	1.283 s
提交时间	2015-03-15 15:44:14	内存使用	2.60 MiB

#include<iostream>
#include<cstdio>
using namespace std;
struct www{int f,l,r,s,w,z;} A[100010];
char ch;
bool flag;
int n,m,i,zj1,zj2,zj3,zj,ROOT,NOW;

inline void ZIG(int &x)
{
	zj3=A[x].f,zj2=A[zj3].s;
	A[zj3].s-=A[x].s,A[zj3].s+=A[A[x].r].s;A[x].s=zj2;
	if(zj3==A[A[zj3].f].l)A[A[zj3].f].l=x;
	else A[A[zj3].f].r=x;A[x].f=A[zj3].f;
	A[zj3].l=A[x].r,A[A[x].r].f=zj3;
	A[zj3].f=x,A[x].r=zj3;
}
inline void ZAG(int &x)
{
	zj3=A[x].f,zj2=A[zj3].s;
	A[zj3].s-=A[x].s,A[zj3].s+=A[A[x].l].s;A[x].s=zj2;
	if(zj3==A[A[zj3].f].l)A[A[zj3].f].l=x;
	else A[A[zj3].f].r=x;A[x].f=A[zj3].f;
	A[zj3].r=A[x].l,A[A[x].l].f=zj3;
	A[zj3].f=x,A[x].l=zj3;
}
inline void splay(int x)
{
	while(A[x].f)
	{
		zj=A[x].f;
		if(!A[zj].f)if(x==A[zj].l)ZIG(x);else ZAG(x);
		else if(x==A[zj].l)
		if(zj==A[A[zj].f].l)ZIG(zj),ZIG(x);else ZIG(x),ZAG(x);
		else if(zj==A[A[zj].f].l)ZAG(x),ZIG(x);else ZAG(zj),ZAG(x);
	}
	ROOT=x;
}

inline void Insert(int x)
{
	NOW=ROOT;
	while(NOW)
	{
		A[zj=NOW].s++;
		if(A[x].w<A[NOW].w)NOW=A[NOW].l;
		else NOW=A[NOW].r;
	}
	if(A[x].w<A[zj].w)A[zj].l=x;else A[zj].r=x;
	A[x].f=zj,A[x].s=1,A[x].l=A[x].r=0;
}
inline void insert_dfs(int x)
{
	if(A[x].l)insert_dfs(A[x].l);
	if(A[x].r)insert_dfs(A[x].r);
	Insert(x);
}
inline void build(int u,int v)
{
	while(A[u].f)u=A[u].f;
	while(A[v].f)v=A[v].f;
	if(u==v)return;
	if(A[u].s<A[v].s)zj=u,u=v,v=zj;
	ROOT=u,insert_dfs(v);
}
void init()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&A[i].w);
		A[i].s=1,A[i].z=i;
	}
	while(m--)
	{
		scanf("%d%d",&zj1,&zj2);
		build(zj1,zj2);
	}
}

inline void Find(int x,int k)
{
	splay(x);NOW=ROOT;zj=0;flag=0;
	while(NOW)
	{
		zj1=zj+A[A[NOW].l].s+1;
		if(zj1>k)NOW=A[NOW].l;
		else if(zj1<k)zj=zj1,NOW=A[NOW].r;
		else{flag=1;break;}
	}
	if(flag)printf("%d\n",A[NOW].z);
	else printf("-1\n");
}
void work()
{
	scanf("%d\n",&m);
	while(m--)
	{
		scanf("%c%d%d\n",&ch,&zj1,&zj2);
		if(ch=='Q')Find(zj1,zj2);
		else build(zj1,zj2);
	}
}
int main()
{
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	init();
	work();
	return 0;
}