题意：
Q 查询与x连通的第k小
B 将两个集合连通
做法：
求集合第k小->值域线段树 集合连通关系->并查集维护 合并集合->线段树合并
注意：线段树的下标是值域 id存储的是 以线段树节点为下标 题中对应的点标号
query中返回的是 那个点的标号 而 l r 是对应的值域
此题值域小 不需要离散化 一定要分清 点标号 值域 与线段树中的点
#include<bits/stdc++.h> using namespace std; #define M 3100005 #define N 100005 #define mid ((l+r)>>1) int sum[M],id[M],ls[M],rs[M],ndnum=0; int rt[N],f[N]; int get(int x) { if(x==f[x]) return x; return f[x]=get(f[x]); } void update(int a) { sum[a]=sum[ls[a]]+sum[rs[a]]; } int add(int a,int l,int r,int pos,int idx) { if(!a) a=++ndnum;//这里是直接新建点 if(l==r) { id[a]=idx; sum[a]++; return a; } if(pos<=mid) ls[a]=add(ls[a],l,mid,pos,idx); else rs[a]=add(rs[a],mid+1,r,pos,idx); update(a); return a; } int merge(int a,int b,int l,int r) { if(!a) return b;//对于不共有的直接返回 if(!b) return a; if(l==r) { id[a]=id[b],sum[a]+=sum[b]; return a; }//递归到叶子结点说明共有 而共有部分就直接合并信息 ls[a]=merge(ls[a],ls[b],l,mid); rs[a]=merge(rs[a],rs[b],mid+1,r); update(a); return a; } int query(int s,int l,int r,int k) { int ans; if(k>sum[s]||!s) return 0;//特判 if(l==r) return id[s]; if(k<=sum[ls[s]]) ans=query(ls[s],l,mid,k); else ans=query(rs[s],mid+1,r,k-sum[ls[s]]); return ans; } int main() { int n,m,a,b,c,Q; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a),rt[i]=add(rt[i],1,n,a,i);//初始时每个点都有一颗线段树 for(int i=1;i<=n;i++) f[i]=i;//并查集一定要记得初始化 for(int i=1;i<=m;i++){ scanf("%d%d",&b,&c); int x=get(b),y=get(c); f[y]=x;//并查集的合并方向一定要和线段树一样！！ rt[x]=merge(rt[x],rt[y],1,n); } scanf("%d",&Q); while(Q--){ char op[2]; scanf("%s",op); scanf("%d%d",&b,&c); if(op[0]=='Q'){ int fa=get(b);//先找父亲 再找线段树的根！！ int ans=query(rt[fa],1,n,c); //一定要写rt[fa] 因为集合的代表元素的点在线段树中的标号是通过++ndnum得来的 而不是其本身 if(!ans) printf("-1 "); else printf("%d ",ans); } else{ int fx=get(b),fy=get(c); if(fx==fy) continue; f[fy]=fx;//找到两个节点的根 合并根的线段树 rt[fx]=merge(rt[fx],rt[fy],1,n); } } } /* 5 1 4 3 2 5 1 1 2 7 Q 3 2 Q 2 1 B 2 3 B 1 5 Q 2 1 Q 2 4 Q 2 3 */