线段树合并好写好调，隔壁老王的treap+启发式合并难写难调
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, fa[100005], val[100005], rot[100005], uu, vv, fan[100005], cnt;
int lson[5000005], rson[5000005], sum[5000005];
char ss[5];
int myfind(int x){
return fa[x]==x?x:fa[x]=myfind(fa[x]);
}
void insert(int &k, int l, int r, int x){
if(!k) k = ++cnt;
if(l==r) sum[k] = 1;
else{
int mid=(l+r)>>1;
if(x<=mid) insert(lson[k], l, mid, x);
if(mid<x) insert(rson[k], mid+1, r, x);
sum[k] = sum[lson[k]] + sum[rson[k]];
}
}
int query(int o, int l, int r, int x){
if(l==r) return l;
int mid=(l+r)>>1;
if(x<=sum[lson[o]]) return query(lson[o], l, mid, x);
else return query(rson[o], mid+1, r, x-sum[lson[o]]);
}
int merge(int x, int y){
if(x==0 || y==0) return x+y;
lson[x] = merge(lson[x], lson[y]);
rson[x] = merge(rson[x], rson[y]);
sum[x] = sum[lson[x]] + sum[rson[x]];
return x;
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d", &val[i]);
fa[i] = i;
fan[val[i]] = i;
}
for(int i=1; i<=m; i++){
scanf("%d %d", &uu, &vv);
fa[myfind(vv)] = myfind(uu);
}
for(int i=1; i<=n; i++)
insert(rot[myfind(i)], 1, n, val[i]);
cin>>m;
while(m--){
scanf("%s", ss);
if(ss[0]=='Q'){
scanf("%d %d", &uu, &vv);
int p=myfind(uu);
if(sum[rot[p]]<vv) printf("-1
");
else printf("%d
", fan[query(rot[p], 1, n, vv)]);
}
else{
scanf("%d %d", &uu, &vv);
int p=myfind(uu), q=myfind(vv);
if(p!=q){
fa[q] = p;
rot[p] = merge(rot[q], rot[p]);
}
}
}
return 0;
}