对每个联通块建一棵线段树，并用并查集维护联通块的根。

先开始WA了几次，要注意每次操作都是对联通块的根进行的。

1 #include
     
       2 #include
      
        3 using namespace std; 4 inline char nc() { 5     static char b[1<<14],*s=b,*t=b; 6     return s==t&&(t=(s=b)+fread(b,1,1<<14,stdin),s==t)?-1:*s++; 7 } 8 inline void read(int &x) { 9     char b = nc(); x = 0;10     for (; !isdigit(b); b = nc());11     for (; isdigit(b); b = nc()) x = x * 10 + b - '0';12 }13 inline void read(char &x) {14     for (x = nc(); x != 'B' && x != 'Q'; x = nc());    15 }16 const int N = 100010;17 int rt[N], ls[N*18], rs[N*18], A, r[N], s[N*18];18 int n, m, fa[N];19 #define lson l, m, ls[rt]20 #define rson m + 1, r, rs[rt]21 int find(int x) {22     return x == fa[x] ? x : fa[x] = find(fa[x]);23 }24 inline void upd(int rt) {25     s[rt] = s[ls[rt]] + s[rs[rt]];26 }27 void add(int p, int l, int r, int &rt) {28     if (!rt) rt = ++A;29     if (l == r) return ++s[rt], void();30     int m = (l + r) >> 1;31     if (p <= m) add(p, lson);32     else add(p, rson);33     upd(rt);34 }35 int merge(int x, int y) {36     if (!x) return y;37     if (!y) return x;38     ls[x] = merge(ls[x], ls[y]);39     rs[x] = merge(rs[x], rs[y]);40     s[x] += s[y];41     return x;42 }43 int query(int k, int l, int r, int rt) {44     if (l == r) return l;45     int m = (l + r) >> 1;46     if (k <= s[ls[rt]]) return query(k, lson);47     else return query(k - s[ls[rt]], rson);48 }49 int query(int x, int k) {50     if (s[rt[x]] < k) return -1;51     return r[query(k, 1, n, rt[x])];52 }53 int main() {54     read(n); read(m);55     for (int i = 1; i <= n; ++i) fa[i] = i;56     for (int t, i = 1; i <= n; ++i)57         read(t), r[t] = i, add(t, 1, n, rt[i]);58     for (int x, y, i = 0; i < m; ++i) {59         read(x), read(y);60         if ((x=find(x)) != (y=find(y))) 61             rt[y] = merge(rt[x], rt[y]), fa[x] = y;62     }63     read(m); char op;64     for (int i = 0, a, b; i < m; ++i) {65         read(op); read(a); read(b);66         if (op == 'B') {
   if ((a=find(a)) != (b=find(b))) rt[b] = merge(rt[a], rt[b]), fa[a] = b;}67         else printf("%d\n", query(find(a), b));68     }69     return 0;70 }