题解：
线段树合并的好题。在这题中我们可以用并查集维护连通块，因为要统计第k大，所以还可以用线段树合并来统计子树之间的信息。
坑点：1：注意炸内存 2：最后输出的是编号，要存起来 3：注意值域线段树中查询第k大的写法
代码如下：
#include<cstdio> using namespace std; const int N=5000005; int root[N]; int n,m; int T; int lc[N],rc[N]; int sum[N]; int fa[N]; int rev[N]; int maxx; int x,y; int o1,o2; int k; int kkk; int val; char opt[2]; int ans; int get(int x){//并查集维护连通块 if(x!=fa[x]) return fa[x]=get(fa[x]); } void build(int &rt,int l,int r,int v){ if(!rt) rt=++T; if(l==r){ sum[rt]++; return; } int mid=(l+r)>>1; if(v<=mid) build(lc[rt],l,mid,v); else build(rc[rt],mid+1,r,v); sum[rt]=sum[lc[rt]]+sum[rc[rt]]; } int merge(int x,int y){ if(!x||!y) return x+y; int now=++T; sum[now]=sum[x]+sum[y]; lc[now]=merge(lc[x],lc[y]); rc[now]=merge(rc[x],rc[y]); return now; } int query(int rt,int l,int r,int k){//查询第k大 if(sum[rt]<k) return 0; if(l==r) return l; int mid=(l+r)>>1; if(sum[lc[rt]]>=k) return query(lc[rt],l,mid,k); else return query(rc[rt],mid+1,r,k-sum[lc[rt]]); } void united(int x,int y){//合并，并查集和线段树一起合并 int f1=get(x); int f2=get(y); if(f1!=f2) fa[f1]=f2; root[f2]=merge(root[f1],root[f2]); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++){ scanf("%d",&val); rev[val]=i; build(root[i],1,n,val); } for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); united(x,y); } scanf("%d",&k); while(k--){ scanf("%s",opt); if(opt[0]=='B'){ scanf("%d%d",&o1,&o2); united(o1,o2); } else{ scanf("%d%d",&o1,&kkk); int ljb=root[get(o1)]; if(sum[ljb]<kkk) printf("-1 "); else printf("%d ",rev[query(ljb,1,n,kkk)]); } } return 0; }