#include <bits/stdc++.h>
#define N 100034
using namespace std;

struct STfr{
    int sz, cnt;
    struct node{int lc, rc, v;}*x;
    int *root, rcnt;
    STfr (int size = 100){x = 0; resize(size);}
    ~STfr (){if(x) delete(x); if(root) delete(root);}
    void resize(int size){
        sz = size; if(x) delete(x); if(root) delete(root);
        int sz0 = (sz << 2) + sz << 3, sz1 = (sz << 1) + sz;
        x = new node[sz0]; memset(x, 0, sz0 << 2);
        root = new int[sz1]; memset(root, 0, sz1 << 2); cnt = rcnt = 0;
    }
    int init(int id, int h){root[++rcnt] = build(h, 1, sz); return rcnt;}
    int merge(int u, int v){root[++rcnt] = merge(root[u], root[v], 1, sz); return rcnt;}
    int range(int rt, int k){return query(root[rt], k, 1, sz);}
    int build(int h, int L, int R){
        int id = ++cnt;
        x[id].v = 1;
        if(L < R){
            int M = L + R - 1 >> 1;
            x[id].lc = x[id].rc = 0;
            h <= M ? x[id].lc = build(h, L, M) : x[id].rc = build(h, M + 1, R);
            x[id].v = 1;
        }
        return id;
    }
    int merge(int i1, int i2, int L, int R){
        if(!(i1 && i2)) return i1 | i2;
        int id = ++cnt;
        if(L < R){
            int M = L + R - 1 >> 1;
            x[id].lc = merge(x[i1].lc, x[i2].lc, L, M);
            x[id].rc = merge(x[i1].rc, x[i2].rc, M + 1, R);
            x[id].v = x[id].lc[x].v + x[id].rc[x].v;
        }else
            x[id].v = x[i1].v + x[i2].v;
        return id;
    }
    int query(int id, int k, int L, int R){
        if(k > x[id].v) return 0;
        if(L == R) return L;
        int M = L + R - 1 >> 1, k0 = x[id].lc[x].v;
        return k <= k0 ? query(x[id].lc, k, L, M) : query(x[id].rc, k - k0, M + 1, R);
    }
};

int n, q;
int i, u, v, U, V;
int w[N], _w[N], p[N], r[N]; // _w is the inverse map of w, p is for union-find, r is for root
char ch;
STfr s;

int ancestor(int x){return p[x] == x ? x : p[x] = ancestor(p[x]);}

int main(){
    scanf("%d%d", &n, &q);
    s.resize(n);
    for(i = 1; i <= n; i++){
        scanf("%d", w + i);
        _w[w[i]] = i;
        p[i] = r[i] = i;
        s.init(i, w[i]);
    }
    for(_w[0] = -1; q; q--){
        scanf("%d%d", &u, &v);
        U = ancestor(u);
        V = ancestor(v);
        if(U != V){
            p[U] = V;
            r[V] = s.merge(r[U], r[V]);
        }
    }
    for(scanf("%d", &q); q; q--){
        do ch = getchar(); while(ch <= ' ');
        scanf("%d%d", &u, &v);
        U = ancestor(u);
        if(ch == 'Q')
            printf("%d\n", _w[s.range(r[U], v)]);
        else
            if(U != (V = ancestor(v))){
                p[U] = V;
                r[V] = s.merge(r[U], r[V]);
            }
    }
    return 0;
}

C68 线段树合并+并查集 P3224 [HNOI2012] 永无乡

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

void read(int &l){ //快读
  l=0; char c=getchar();
  while(!isdigit(c))c=getchar();
  while(isdigit(c))l=l*10+c-'0',c=getchar();
}
const int N=100005;
#define mid (l+r)/2
int n,m,q,f[N];  //f:并查集
int root[N],tot; //根节点,开点个数
int ls[N*20],rs[N*20],id[N*20],sum[N*20];
//id:节点编号，sum:重要度的出现次数之和

int find(int x){ //找根
  return x==f[x]?x:f[x]=find(f[x]);
}
void pushup(int u){ //上传
  sum[u]=sum[ls[u]]+sum[rs[u]];
}
int change(int u,int l,int r,int p,int i){ //点修
  if(!u) u=++tot;
  if(l==r){id[u]=i; sum[u]++; return u;}
  if(p<=mid) ls[u]=change(ls[u],l,mid,p,i); else rs[u]=change(rs[u],mid+1,r,p,i);
  pushup(u); return u;
}
int merge(int x,int y){ //合并
  if(!x||!y) return x+y;
  ls[x]=merge(ls[x],ls[y]);
  rs[x]=merge(rs[x],rs[y]);
  pushup(x); return x;
}
int query(int u,int l,int r,int k){ //点查
  if(l==r) return id[u];
  int ans=0;
  if(k<=sum[ls[u]]) ans=query(ls[u],l,mid,k);
  else ans=query(rs[u],mid+1,r,k-sum[ls[u]]);
  return ans;
}
int main(){
  read(n);read(m); int x,y;
  for(int i=1;i<=n;i++){
    f[i]=i; read(x);
    root[i]=change(root[i],1,n,x,i);
  }
  for(int i=1;i<=m;i++){
    read(x);read(y);x=find(x);y=find(y);
    if(x==y) continue;
    f[y]=x;
    root[x]=merge(root[x],root[y]);
  }
  read(q);
  while(q--){
    char ch[2]; scanf("%s",ch);
    if(ch[0]=='B'){
      read(x);read(y); 
      x=find(x);y=find(y);
      if(x==y) continue;
      f[y]=x;
      root[x]=merge(root[x],root[y]);
    }
    else{
      read(x);read(y); x=find(x);
      int ans=query(root[x],1,n,y);
      ans=ans?ans:-1; printf("%d\n",ans);
    }
  }
}