首先对于一个连通块中，询问我们可以直接用平衡树来求出排名，那么我们可以用并查集来维护各个块中的连通情况，对于合并两个平衡树，我们可以暴力的将size小的平衡树中的所有节点删掉，然后加入大的平衡树中，因为每个点只可能被删除插入logn次，所以时间复杂度为nlog^2n。
/************************************************************** Problem: 2733 User: BLADEVIL Language: C++ Result: Accepted Time:2112 ms Memory:64868 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #define maxn 100010 #define maxt 4000010 using namespace std; int n,m; int father[maxn],a[maxn],root[maxn]; int left[maxt],right[maxt],size[maxt],key[maxt]; int tot,save; int adr[maxn]; int getfather(int x) { if (father[x]==x) return x; return father[x]=getfather(father[x]); } void swap(int &x,int &y) { int z=x; x=y; y=z; } void left_rotate(int &t) { int k=right[t]; right[t]=left[k]; left[k]=t; size[k]=size[t]; size[t]=size[left[t]]+size[right[t]]+1; t=k; } void right_rotate(int &t) { int k=left[t]; left[t]=right[k]; right[k]=t; size[k]=size[t]; size[t]=size[left[t]]+size[right[t]]+1; t=k; } void maintain(int &t,bool flag) { if (!flag) { if (size[left[left[t]]]>size[right[t]]) right_rotate(t); else if (size[right[left[t]]]>size[right[t]]) left_rotate(left[t]),right_rotate(t); else return; } else { if (size[right[right[t]]]>size[left[t]]) left_rotate(t); else if (size[left[right[t]]]>size[left[t]]) right_rotate(right[t]),left_rotate(t); else return; } maintain(left[t],0); maintain(right[t],1); maintain(t,1); maintain(t,0); } void t_insert(int &t,int v) { if (!t) { t=++tot; left[t]=right[t]=0; key[t]=v; size[t]=1; } else { size[t]++; if (v>key[t]) t_insert(right[t],v); else t_insert(left[t],v); maintain(t,v>key[t]); } } int t_delete(int &t,int v) { size[t]--; if ((key[t]==v)||((v>key[t])&&(!right[t]))||((v<key[t])&&(!left[t]))) { save=key[t]; if ((!left[t])||(!right[t])) t=left[t]+right[t]; else key[t]=t_delete(left[t],v+1); } else return (v>key[t])?t_delete(right[t],v):t_delete(left[t],v); } int t_rank(int &t,int k) { if (size[left[t]]+1==k) return key[t]; return (k<=size[left[t]])?t_rank(left[t],k):t_rank(right[t],k-size[left[t]]-1); } void combine(int x,int y) { int fx,fy; fx=getfather(x); fy=getfather(y); if (size[root[fx]]<size[root[fy]]) swap(fx,fy); father[fy]=fx; if (fx!=fy) { fy=root[fy]; while (root[fy]) { t_insert(root[fx],a[fy]); t_delete(root[fy],a[fy]); } } } void ask(int x,int k) { x=root[getfather(x)]; if (size[x]>=k) printf("%d ",adr[t_rank(x,k)]); else printf("-1 "); } void init() { int x,y; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) adr[a[i]]=i; for (int i=1;i<=n;i++) father[i]=i,t_insert(root[i],a[i]); while (m--) { scanf("%d%d",&x,&y); combine(x,y); } } void solve() { int test,x,y; char s[10]; scanf("%d",&test); while (test--) { scanf("%s%d%d",&s,&x,&y); if (s[0]=='B') combine(x,y); else ask(x,y); } } int main() { init(); solve(); return 0; }