分析
和主席树不同的是，线段树合并后原树的信息不会保留，
这样就保证空间和常数都比较小，这题比较裸，直接上代码
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=100011; int Tree_Tot;
int n,m,rt[N],w[N*20],p[N*20];
int Ls[N*20],Rs[N*20],f[N];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}
inline signed update(int k,int l,int r,int x,int z){
if (!k) k=++Tree_Tot;
if (l==r) {w[k]=1,p[k]=z; return k;}
rr int mid=(l+r)>>1;
if (x<=mid) Ls[k]=update(Ls[k],l,mid,x,z);
else Rs[k]=update(Rs[k],mid+1,r,x,z);
w[k]=w[Ls[k]]+w[Rs[k]];
return k;
}
inline signed Merge(int fi,int se,int l,int r){
if (!fi||!se) return fi|se;
if (l==r) {if (p[se]) p[fi]=p[se],w[fi]+=w[se]; return fi;}
rr int mid=(l+r)>>1;
Ls[fi]=Merge(Ls[fi],Ls[se],l,mid);
Rs[fi]=Merge(Rs[fi],Rs[se],mid+1,r);
w[fi]=w[Ls[fi]]+w[Rs[fi]];
return fi;
}
inline signed query(int k,int l,int r,int kth){
if (w[k]<kth||!k) return 0;
if (l==r) return p[k];
rr int mid=(l+r)>>1;
if (kth<=w[Ls[k]]) return query(Ls[k],l,mid,kth);
else return query(Rs[k],mid+1,r,kth-w[Ls[k]]);
}
signed main(){
n=iut(); m=iut();
for (rr int i=1;i<=n;++i)
f[i]=i,rt[i]=update(rt[i],1,n,iut(),i);
for (rr int i=1;i<=m;++i){
rr int fa=getf(iut()),fb=getf(iut());
if (fa==fb) continue;
if (fa>fb) fa^=fb,fb^=fa,fa^=fb;
f[fa]=fb,rt[fb]=Merge(rt[fb],rt[fa],1,n);
}
for (rr int Q=iut();Q;--Q){
rr char c=getchar();
while (c!='B'&&c!='Q') c=getchar();
if (c=='B'){
rr int fa=getf(iut()),fb=getf(iut());
if (fa==fb) continue;
if (fa>fb) fa^=fb,fb^=fa,fa^=fb;
f[fa]=fb,rt[fb]=Merge(rt[fb],rt[fa],1,n);
}else{
rr int x=getf(iut()),kth=iut();
rr int t=query(rt[x],1,n,kth);
if (!t) printf("-1"); else print(t);
putchar(10);
}
}
return 0;
}