权值线段树+并查集
对于每一个点先建立一个权值线段树，之后并查集维护/更改连通性。
不知道权值线段树是啥的戳我
联通就直接把祖先连起来然后合并线段树
#include<cstdio> #include<iostream> using namespace std; const int N=100005; int size[N*20],n,m,fa[N],type,q,root[N],w[N],rev[N],ls[N*20],rs[N*20]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; } int findf(int x) { if(x==fa[x])return x; fa[x]=findf(fa[x]); return fa[x]; } void add(int &k,int l,int r,int val) { if(!k)k=++type; if(l==r) { size[k]=1; return ; } int mid=l+r>>1; if(val<=mid)add(ls[k],l,mid,val); else add(rs[k],mid+1,r,val); size[k]=size[ls[k]]+size[rs[k]]; } 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]); size[x]=size[ls[x]]+size[rs[x]]; return x; } int query(int k,int l,int r,int val) { if(l==r)return l; int mid=l+r>>1,sz=size[ls[k]]; if(sz>=val)return query(ls[k],l,mid,val); else return query(rs[k],mid+1,r,val-sz); } int main() { n=read();m=read(); for(int i=1;i<=n;i++)w[i]=read(),fa[i]=i,rev[w[i]]=i; for(int i=1;i<=m;i++) { int x=read(),y=read(); int r1=findf(x),r2=findf(y); fa[r1]=r2; } for(int i=1;i<=n;i++) { int r=findf(i); add(root[r],1,n,w[i]); } q=read(); char op[3]; for(int i=1;i<=q;i++) { scanf("%s",op); int x=read(),y=read(); if(op[0]=='B') { int r1=findf(x),r2=findf(y); if(r1!=r2) { fa[r2]=r1; merge(root[r1],root[r2]); } } else { int r=findf(x); if(size[root[r]]<y)puts("-1"); else { r=query(root[r],1,n,y); printf("%d ",rev[r]); } } } return 0; }