- /**************************************************************
- Problem: 2733
- User: weeping
- Language: C++
- Result: Accepted
- Time:4908 ms
- Memory:4436 kb
- ****************************************************************/
-
- #include < bits / stdc++.h >
-
- using namespace std;
-
- #define lc ch[x][0]#define rc ch[x][1]
-
- int n,
- m,
- q,
- f[100005];
-
- int fd(int x) {
- return f[x] == x ? x: f[x] = fd(f[x]);
- }
-
- struct SplayTree {
-
- const static int maxn = 1e5 + 15;
-
- int tot,
- root,
- ch[maxn][2],
- key[maxn],
- val[maxn],
- sz[maxn],
- rev[maxn],
- fa[maxn];
-
- inline void init(int x, int ky, int v = 0, int par = 0) {
- lc = rc = 0,
- fa[x] = par,
- key[x] = ky,
- val[x] = v,
- sz[x] = 1,
- rev[x] = 0;
- }
-
- inline void init() {
- init(0, 0, 0);
- sz[0] = 0;
- tot = root = 0;
- }
-
- inline void push_up(int x) {
- sz[x] = sz[lc] + sz[rc] + 1;
- }
-
- inline void reverse(int x) {
- rev[x] ^= 1,
- swap(lc, rc);
- }
-
- inline void push_down(int x) {
- if (rev[x]) {
- if (lc) reverse(lc);
- if (rc) reverse(rc);
- rev[x] = 0;
- }
- }
-
- void rotate(int x) {
- int f = fa[x],
- gf = fa[f];
- int t1 = (ch[f][1] == x),
- t2 = (ch[gf][1] == f);
- if (gf) ch[gf][t2] = x;
- fa[x] = gf,
- ch[f][t1] = ch[x][1 ^ t1],
- fa[ch[f][t1]] = f;
- ch[x][t1 ^ 1] = f,
- fa[f] = x;
- push_up(f),
- push_up(x);
- }
-
- void splay(int x, int tar) {
- for (int f = fa[x], gf = fa[f]; f != tar; rotate(x), f = fa[x], gf = fa[f]) if (gf != tar) rotate(((ch[f][1] == x) == (ch[gf][1] == f)) ? f: x);
- if (!tar) root = x;
- }
-
- void insert(int ky, int v) {
- int x = root,
- ls = root;
- while (x) {
- push_down(x);
- sz[x]++,
- ls = x;
- x = ch[x][ky > key[x]];
- }
- init(++tot, ky, v, ls);
- ch[ls][ky > key[ls]] = tot;
- splay(tot, 0);
- }
-
- int find(int ky) {
- int x = root;
- while (x) {
- push_down(x);
- if (key[x] == ky) break;
- x = ch[x][ky > key[x]];
- }
- if (x) splay(x, 0);
- else x = -1;
- return x;
- }
-
- // Delete Root
- void Delete() {
- if (!ch[root][0]) {
- fa[ch[root][1]] = 0;
- root = ch[root][1];
- } else {
- int cur = ch[root][0];
- while (ch[cur][1]) cur = ch[cur][1];
- splay(cur, root);
- ch[cur][1] = ch[root][1];
- root = cur,
- fa[cur] = 0,
- fa[ch[root][1]] = root;
- push_up(root);
- }
- }
-
- int kth(int k) {
- int x = root;
- if (sz[x] < k) return - 1;
- while (x) {
- push_down(x);
- if (k == sz[lc] + 1) break;
- if (k > sz[lc]) k -= sz[lc] + 1,
- x = rc;
- else x = lc;
- }
- if (x) splay(x, 0);
- else x = -1;
- return x;
- }
-
- int pred(void) {
- int x = root;
- if (!x || !lc) return - 1;
- x = lc;
- while (rc) push_down(x),
- x = rc;
- splay(x, 0);
- return x;
- }
-
- int succ(void) {
- int x = root;
- if (!x || !rc) return - 1;
- x = rc;
- while (lc) push_down(x),
- x = lc;
- splay(x, 0);
- return x;
- }
-
- void debug(int x) {
- if (!x) return;
- if (lc) debug(lc);
- printf("%d ", key[x]);
- if (rc) debug(rc);
- }
-
- void qinsert(int y) {
- int x = root,
- ls = root,
- ky = key[y];
- while (x) ls = x,
- x = ch[x][ky > key[x]];
- x = ls;
- ch[x][ky > key[x]] = y,
- fa[y] = x,
- sz[y] = 1;
- splay(y, 0);
- }
-
- void qmerge(int x) {
- if (!x) return;
- int tl = lc,
- tr = rc;
- lc = rc = 0;
- qmerge(tl);
- qinsert(x);
- qmerge(tr);
- }
- void merge(int u, int v) {
- if (u == v) return;
- if (sz[u] > sz[v]) swap(u, v);
- f[u] = v,
- splay(v, 0);
- qmerge(u);
- }
- }
- sp;
-
- int main(void) {
- scanf("%d%d", &n, &m);
- for (int i = 1, x; i <= n; i++) scanf("%d", &x),
- f[i] = i,
- sp.key[i] = x,
- sp.sz[i] = 1;
- for (int i = 1, u, v; i <= m; i++) scanf("%d%d", &u, &v),
- sp.merge(fd(u), fd(v));
- scanf("%d", &q);
- char op[5];
- for (int i = 1, x, y; i <= q; i++) {
- scanf("%s%d%d", op, &x, &y);
- if (op[0] == ‘B‘) sp.merge(fd(x), fd(y));
- else sp.splay(x, 0),
- printf("%d\n", sp.kth(y));
- }
- return 0;
- }