记录编号	357740	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.014 s
提交时间	2016-12-12 11:57:59	内存使用	1.51 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <cctype>
#include <ctime>
using namespace std;
namespace IO
{
    char buf[1<<16], *fs, *ft;
    inline char readc()
    {
        return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<16,stdin), fs==ft))?0:*fs++;
    }
    inline int fast_read()
    {
        char c = readc();
        int r = 0;
        bool sig = false;
        while(c > '9' || c < '0')
        {
            if(c == '-')sig = true;
            c = readc();
        }
        while(c >= '0' && c <= '9')
        {
            r = (r<<3)+(r<<1)+(c^0x30);
            c = readc();
        }
        return sig?-r:r;
    }
}using IO::fast_read;using IO::readc;

struct node
{
    node *ls, *rs;
    int size;
    int fix, key, value;
    #define SIZE(x) ((x)?(x)->size:0)
    inline node(int k, int v = 0):fix(rand()), key(k), value(v), size(1)
    {
        ls = rs = NULL;
    }
    inline void pushup()
    {
        size = 1+SIZE(ls)+SIZE(rs);
    }
};
typedef node *pnode;
typedef pair<node*, node*> droot;
node *merge(node *a, node *b)
{
    if(!a)return b;
    if(!b)return a;
    if(a->fix < b->fix)
    {
        a->rs = merge(a->rs, b);
        a->pushup();
        return a;
    }else
    {
        b->ls = merge(a, b->ls);
        b->pushup();
        return b;
    }
}
droot split(node *x, int k)
{
    if(!x)return droot(NULL, NULL);
    droot r;
    if(SIZE(x->ls) >= k)
    {
        r = split(x->ls, k);
        x->ls = r.second;
        x->pushup();
        r.second = x;
    }else
    {
        r = split(x->rs, k-SIZE(x->ls)-1);
        x->rs = r.first;
        x->pushup();
        r.first = x;
    }
    return r;
}
node* kth(node *x, int k)
{
    while(x)
    {
        if(k == SIZE(x->ls)+1)return x;
        else if(k < SIZE(x->ls)+1)x = x->ls;
        else
        {
            k -= SIZE(x->ls)+1;
            x = x->rs;
        }
    }
    return NULL;
}
int rank(node *x, int v)
{
    if(!x)return 0;
    if(v < x->key)return rank(x->ls, v);
    else return SIZE(x->ls)+1+rank(x->rs, v);
}
node *insert(node *root, node *is)
{
    int k = rank(root, is->key);
    droot p = split(root, k);
    node *nd = new node(is->key, is->value);
    return merge(merge(p.first, nd), p.second);
}
pnode ts[100002];
int f[100002];
int size[100002];
int findf(int x){return x==f[x]?x:f[x]=findf(f[x]);}
void link(node *&x, node *y) //x <-- y
{
    if(!y)return;
    x = insert(x, y);
    link(x, y->ls);
    link(x, y->rs);
}
void unit(int x, int y)
{
    x = findf(x), y = findf(y);
    if(x == y)return;
    if(size[x] < size[y])swap(x, y);
    f[y] = x;
    size[x] += size[y];
    link(ts[x], ts[y]);
    ts[y] = NULL;
}
int main()
{
    freopen("bzoj_2733.in", "r", stdin);
    freopen("bzoj_2733.out", "w", stdout);
    srand(time(NULL));
    int n = fast_read();
    int m = fast_read();
    for(int i = 1; i <= n; i++)
    {
        ts[i] = new node(fast_read(), i);
        f[i] = i;
        size[i] = 1;
    }
    while(m--)
    {
        int x = fast_read();
        int y = fast_read();
        unit(x, y);
    }
    int q = fast_read();
    while(q--)
    {
        char c;
        while(!isalpha(c = readc()));
        if(c == 'Q')
        {
            int x = fast_read();
            int k = fast_read();
            node *p = ts[findf(x)];
            if(!p || k > p->size)puts("-1");
            else printf("%d\n", kth(p, k)->value);
        }else if(c == 'B')
        {
            int x = fast_read();
            int y = fast_read();
            unit(x, y);
        }
    }
    return 0;
}