线段树合并+并查集
在每一个联通块上建一个权值线段树
每次用并查集判断维护，线段树合并即可
相当于每一次询问都在这个联通块一个线段树上问区间第k小
#include <bits/stdc++.h> using namespace std; const int MAXN=2*1e5+100; int n,m,q,rk[MAXN],fa[MAXN],root[MAXN]; int t,f[MAXN]; struct node { int lc,rc,sum; }sh[MAXN*15]; int getfather(int x)//并查集 { if (fa[x]==x) return x; fa[x]=getfather(fa[x]); return fa[x]; } void insert(int &x,int l,int r,int where) { if (!x) { t++; x=t; } if (l==r) { sh[x].sum=1; return; } int mid; mid=(l+r)/2; if (where<=mid) insert(sh[x].lc,l,mid,where); else insert(sh[x].rc,mid+1,r,where); sh[x].sum=sh[sh[x].lc].sum+sh[sh[x].rc].sum; } int merge(int u,int v)//线段树合并 { if (!u) return v; if (!v) return u; sh[u].lc=merge(sh[u].lc,sh[v].lc); sh[u].rc=merge(sh[u].rc,sh[v].rc); sh[u].sum=sh[sh[u].lc].sum+sh[sh[u].rc].sum; return u; } int query(int x,int l,int r,int k) { if (l==r) return l; int mid; mid=(l+r)/2; if (sh[sh[x].lc].sum>=k) return query(sh[x].lc,l,mid,k); else return query(sh[x].rc,mid+1,r,k-sh[sh[x].lc].sum); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d",&rk[i]); f[rk[i]]=i; fa[i]=i; } for (int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); if (getfather(u)!=getfather(v)) { fa[getfather(u)]=getfather(v); } } for (int i=1;i<=n;i++) { insert(root[getfather(i)],1,n,rk[i]);//联通块上建线段树 } scanf("%d",&q); for (int i=1;i<=q;i++) { int a,b; char ch[10]; scanf("%s%d%d",ch,&a,&b); if (ch[0]=='Q') { int father; father=getfather(a); if (sh[root[father]].sum<b) { printf("-1\n"); } else { printf("%d\n",f[query(root[father],1,n,b)]);//找第k小数 } } else { if (getfather(a)!=getfather(b)) { root[getfather(a)]=merge(root[getfather(b)],root[getfather(a)]); fa[getfather(a)]=getfather(b);//并查集维护 } } } }