最重要的思想是，线段树里存的是值为L到R的个数，即在L-R这段区间内，值为L，L+1，L+2，L+3…R的个数。
#include<cstdio> #include<cstring> const int maxn = 2e5+10; #define mid (l+r)>>1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int sum[maxn<<2];//记录L到R的范围内，值为L，L+1，L+2...R-1,R的个数 int a[maxn],p[maxn]; int n; void build(int l,int r,int rt) { if(l==1) sum[rt]=n;//若有10个点，则值为1的点有10个 else sum[rt]=0;//其他值都为0 if(l==r) return ; int m=mid; build(lson); build(rson); } void update(int l,int r,int rt,int val,bool flag) { if(!flag) sum[rt]--; else sum[rt]++; int m=mid; if(l==r) return ; if(val<=m) update(lson,val,flag); else update(rson,val,flag); } int find(int x) { return x==p[x] ? x : p[x]=find(p[x]); } void query(int l,int r,int rt,int k) { if(l==r) { printf("%d\n",l); return ; } int m=mid; if(k<=sum[rt<<1|1]) query(rson,k);//右子树有大于等于k个数，第k个数肯定在右边 else query(lson,k-sum[rt<<1|1]); } int main() { int i,m,q,x,y,k; scanf("%d%d",&n,&m); for(i=1; i<=n; i++) { a[i]=1; //根据题意，初始化每个点的值 p[i]=i; //存每个点的父节点 } build(1,n,1); //建树 for(i=1; i<=m; i++) { scanf("%d",&q); if(q==0) { scanf("%d%d",&x,&y); x=find(x); //查找x的父节点 y=find(y); //查找y的父节点 if(x==y) //如果x和y已经属于一个组，就不用再合并 continue; update(1,n,1,a[x],false); //将记录值为a[x]有几个数的点减1 update(1,n,1,a[y],false); update(1,n,1,a[x]+a[y],true); //将值为a[x]+a[y]的点加1 p[y]=x; //并查集，将x和y归为一组 a[x]+=a[y]; //用a[x]记录这个组的值为多少 } else { scanf("%d",&k); query(1,n,1,k); } } return 0; }