<\/p>\n
\u7565\u3002\uff09<\/p>\n
\u5e73\u8861\u6811\u542f\u53d1\u5f0f\u5408\u5e76\u3002<\/p>\n
\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e5) + 9;\r\n\r\nnamespace SBT{\r\n const int NN = int(1e5) + 9;\r\n int c[2][NN], sz[NN], ky[NN], tot;\r\n#define lx l[x]\r\n#define rx r[x]\r\n#define l c[d]\r\n#define r c[!d]\r\n#define kx ky[x]\r\n#define sx sz[x]\r\n#define d 0\r\n int new_node(int v = 0){\r\n int x=++tot;lx=rx=0;\r\n sx=1;kx=v;\r\n return x;\r\n }\r\n\r\n void upd(int x){\r\n sx=sz[lx]+1+sz[rx];\r\n }\r\n#undef d\r\n void rot(int &x,int d){\r\n int y=rx;rx=l[y];l[y]=x;\r\n upd(x),upd(y),x=y;\r\n }\r\n\r\n void fix(int &x,int d){\r\n if (sz[l[lx]] > sz[rx]) rot(x,!d);\r\n else{\r\n if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);\r\n else return;\r\n }\r\n d=0,fix(lx,0),fix(rx,1);\r\n fix(x,0),fix(x,1);\/\/upd(x);\r\n }\r\n#define d 0\r\n\r\n int mini(int x){\r\n if (lx) return mini(lx);\r\n return ky[x];\r\n }\r\n\r\n void iod(int x){\r\n if (!x) return;\r\n iod(lx); printf("%d ", ky[x]); iod(rx);\r\n }\r\n\r\n void Ins(int &x,int v){\r\n if(!x) x = new_node(v);\r\n else{\r\n Ins(c[v>kx][x],v);\r\n fix(x,v>=kx);\r\n }\r\n upd(x);\r\n }\r\n\r\n void Ins2(int &x, int xx){\r\n if (!x) x = xx;\r\n else{\r\n Ins2(c[ky[xx]>kx][x], xx);\r\n fix(x, ky[xx] >= kx);\r\n }\r\n upd(x);\r\n }\r\n\r\n int d_key; void Del(int &x,int v){\r\n --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){\r\n if(!lx||!rx) d_key = kx, x = lx | rx;\r\n else Del(lx,v+1), kx = d_key;\r\n }\r\n else Del(c[v>kx][x],v);\r\n }\r\n\r\n int Rank(int x,int v){\r\n int z=0;while(x){\r\n if(kx<v){\r\n z+=sz[lx]+1;\r\n x=rx;\r\n }\r\n else x=lx;\r\n }\r\n return z;\r\n }\r\n\r\n int Select(int x,int k){\r\n if (sz[lx] == k) return x;\r\n return sz[lx]>k?Select(lx,k):Select(rx,k-sz[lx]-1);\r\n }\r\n\r\n bool Find(int x,int v){\r\n if (!x) return 0;if (kx==v) return 1;\r\n return Find(c[v>kx][x],v);\r\n }\r\n\r\n void Init(){\r\n tot = 0;\r\n }\r\n\r\n int Q[N], cz, op;\r\n\r\n void Merge(int x, int& y){ \/\/ x -> y\r\n cz = 0, op = 1; Q[cz] = x;\r\n while (cz < op){\r\n x = Q[cz++];\r\n if (lx) Q[op++] = lx;\r\n if (rx) Q[op++] = rx;\r\n lx = rx = 0;\r\n Ins2(y, x);\r\n }\r\n }\r\n\r\n#undef d\r\n#undef l\r\n#undef r\r\n#undef lx\r\n#undef rx\r\n#undef sx\r\n#undef kx\r\n} \/\/using namespace SBT;\r\n\r\n\r\nint T[N], P[N], sz[N]; \/\/ DSU\r\nint n;\r\n\r\nint Find(int x){\r\n return P[x] == x ? x : P[x] = Find(P[x]);\r\n}\r\n\r\nvoid Union(int x, int y){\r\n x = Find(x), y = Find(y); if (x == y) return;\r\n if (sz[T[x]] > sz[T[y]]) swap(x, y);\r\n P[x] = y; SBT::Merge(T[x], T[y]);\r\n}\r\n\r\nvoid Init(){\r\n SBT::Init(); int m; RD(n, m);\r\n REP_1(i, n) T[i] = SBT::new_node(RD()), P[i] = i, sz[i] = 1;\r\n DO(m){\r\n int x, y; RD(x, y);\r\n Union(x, y);\r\n }\r\n}\r\n\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n\r\n Init(); Rush{\r\n char cmd; int x, y;\r\n RC(cmd); RD(x, y);\r\n if (cmd == 'B'){\r\n Union(x, y);\r\n }\r\n else{\r\n x = Find(x);\r\n if (y > SBT::sz[T[x]]){\r\n OT(-1);\r\n }\r\n else{\r\n --y;\r\n OT(SBT::Select(T[x], y));\r\n }\r\n }\r\n }\r\n}\r\n<\/pre>\nReferences: <\/h3>\n