题解：
splay，维护当前第k大
并查集维护当前集合
合并x,y时，del(num[x]),del(num[y]),insert(num[x]+num[y])
代码：
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int N=400005; int pre[N],tot,xx,q,size[N],c[N][2],fa[N],data[N],root,n,m,x,y,num[N]; void rot(int x) { int y=pre[x],k=(c[y][0]==x); size[y]=size[c[y][k]]+size[c[x][k]]+1; size[x]=size[c[x][!k]]+size[y]+1; c[y][!k]=c[x][k]; pre[c[y][!k]]=y; pre[x]=pre[y]; if(pre[y])c[pre[y]][c[pre[y]][1]==y]=x; c[x][k]=y;pre[y]=x; } void splay(int x,int g) { for(int y=pre[x];y!=g;rot(x),y=pre[x]) if(pre[y]!=g)rot((x==c[y][0])==(y==c[pre[y]][0])?y:x); if(g==0)root=x; } void insert(int x) { int y=root; while(c[y][x>data[y]]) y=c[y][x>data[y]]; data[++tot]=x; c[tot][0]=c[tot][1]=0; pre[tot]=y; if(y)c[y][x>data[y]]=tot; splay(tot,0); } void del(int x) { int y=root; while(data[y]!=x) y=c[y][x>data[y]]; splay(y,0); y=c[root][1]; bool b; if(!y) b=1,y=c[root][0];else b=0; while(c[y][b]) y=c[y][b]; splay(y,root); c[y][b]=c[root][b];pre[c[root][b]]=y;pre[y]=0;root=y; size[y]=size[c[y][!b]]+size[c[y][b]]; } int find(int x) { if (x==fa[x])return x; return fa[x]=find(fa[x]); } int findkth(int x) { int y=root; while(x) if(size[c[y][0]]+1<x)x-=size[c[y][0]]+1,y=c[y][1]; else if(size[c[y][0]]+1==x) return data[y]; else y=c[y][0]; return data[y]; } int read() { char c;int x=0; for (;c<'0'||c>'9';c=getchar()); for (;c>='0'&&c<='9';c=getchar())x=x*10+c-48; return x; } void write(int x) { if (x>=10)write(x/10); putchar(x%10+48); } int main() { n=read();m=read(); for (int i=1;i<=n;i++)insert(1); for (int i=1;i<=n;i++)fa[i]=i,num[i]=1; while (m--) { xx=read(); if (xx==0) { x=read();y=read(); int dx=find(x),dy=find(y); if (dx!=dy) { fa[dx]=dy; del(num[dy]);del(num[dx]); num[dy]+=num[dx]; insert(num[dy]); n--; } } else { x=read(); write(findkth(n-x+1)),puts(""); } } }