思路很简单，树状数组+并查集维护，然后二分乱搞就行了。
贴：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=200001;
int n,m,tree[MAXN],cat[MAXN],father[MAXN],num;
int lowbit(int x){
	return x&-x;
}
int getfather(int x){
	return father[x]==x?x:father[x]=getfather(father[x]);
}
void add(int x,int delta){
	while(x<=n){
		tree[x]+=delta;
		x+=lowbit(x);
	}
}
int sum(int x){
	int Sum=0;
	while(x){
		Sum+=tree[x];
		x-=lowbit(x);
	}
	return Sum;
}
int find(int l,int r,int x){
	int mid=(l+r)/2;
	if(l>=r) return mid+(sum(mid)<x?1:0);
	if(sum(mid)>=x) return find(l,mid-1,x);
	if(sum(mid)<x) return find(mid+1,r,x);
}
int main()
{
	scanf("%d%d",&n,&m);
	num=n;
	for(int i=1;i<=n;i++) father[i]=i;
	for(int i=1;i<=n;i++) cat[i]=1;
	add(1,n);
	for(int i=1;i<=m;i++)
	{
		int temp;
		scanf("%d",&temp);
		if(temp)
		{
			int a;
			scanf("%d",&a);
			printf("%d\n",find(1,n,num-a+1));
		}
		else
		{
			int a,b,fa,fb;
			scanf("%d%d",&a,&b);
			fa=getfather(a);
			fb=getfather(b);
			if(fa==fb) continue;
			num--;
			father[fa]=fb;
			add(cat[fa],-1);
			add(cat[fb],-1);
			cat[fb]+=cat[fa];
			add(cat[fb],1);
			fa=getfather(a);
		}
	}
}