记录编号	540688	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.701 s
提交时间	2019-08-27 23:34:50	内存使用	23.40 MiB

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=1e5+7;
using namespace __gnu_pbds;
int imp[N],fa[N];
void init_set(int n)
{
    for(int i=1;i<=n;++i)  fa[i]=i;
}
int find(int x)
{
   	if (fa[x]!=x) return fa[x]=find(fa[x]);
   	return fa[x];
}

void uni_set(int x,int y)
{
    x=find(x),y=find(y);  fa[x]=y;
}
typedef tree<int,int,std::greater<int>,rb_tree_tag,
     tree_order_statistics_node_update> Tree;
Tree block[N];
void init_tree(int n)
{
    for(int i=1;i<=n;++i)
        block[find(i)].insert(std::pair<int,int>(imp[i],i));
}

void uni_tree(int x,int y)
{
    x=fa[x],y=fa[y];
    if(x==y) return;
    int size_x=block[x].size(),size_y=block[y].size();
    if(size_x>size_y)std::swap(x,y);
    Tree::point_iterator it=block[x].begin();
    for(;it!=block[x].end();++it)
    {
        block[y].insert(std::pair<int,int>(it->first,it->second));
        block[x].erase(it);
    }
    uni_set(x,y);
}
int main()
{
    freopen("bzoj_2733.in","r",stdin);
    freopen("bzoj_2733.out","w",stdout);
	int n=read(),m=read();init_set(n);
    for(int i=1;i<=n;++i) imp[i]=read();
    for(int i=0;i<m;++i) uni_set(read(),read());
    init_tree(n);
    int Q=read();
    char opt[5];
    while (Q--)
    {
        scanf("%s",opt);
        if(opt[0]=='B')  uni_tree(read(),read());
        else
        {
            int father=find(read());
            int k=read();
            if(k>block[father].size()) puts("-1");
            else printf("%d\n",block[father].find_by_order(block[father].size()-k)->second);
        }
    }
    return 0;
}