题意：1~n个猫，有合并操作，有询问操作，合并两只猫所在的集合，询问第K大的集合。
分析：合并操作用并查集，用size维护，询问操作用Treap。注意优化，不能刚开始就把所有size = 1放到名次树中，是1的不做处理，而是不够的时候返回一个1；
#include <cstdio>
#include <algorithm>
#include <cstring> using namespace std; struct Node {
Node *ch[];
int r;
int v;
int s;
Node(int v):v(v) {ch[]=ch[] = NULL;r=rand();s=;}
bool operator < (const Node& rhs) const {
return r < rhs.r;
} int cmp(int x) const {
if(x==v) return -;
return x < v ? : ;
} void maintain() {
s = ;
if(ch[]!=NULL) s+=ch[]->s;
if(ch[]!=NULL) s+=ch[]->s;
} }*root; void rotate(Node* &o,int d)
{
Node *k=o->ch[d^];
o->ch[d^]=k->ch[d];
k->ch[d]=o;
o->maintain();
k->maintain();
o=k;
}
void insert(Node* &o,int v)//可插入重复值
{
if(o==NULL) o=new Node(v);
else
{
int d=v < o->v? :;
insert(o->ch[d],v);
if(o->ch[d]->r > o->r)
rotate(o,d^);
}
o->maintain();
}
void remove(Node* &o,int v)
{
int d=o->cmp(v);
if(d==-)
{
Node *u=o;
if(o->ch[] && o->ch[])
{
int d2= o->ch[]->r < o->ch[]->r ?:;
rotate(o,d2);
remove(o->ch[d2],v);
}
else
{
if(o->ch[]==NULL) o=o->ch[];
else o=o->ch[];
delete u;
}
}
else remove(o->ch[d],v);
if(o) o->maintain();
} int kth(Node *o,int k)//返回第k大的值,不是第k小
{
if(o==NULL || k<= || k> o->s) return ;
int s = (o->ch[]==NULL)?:o->ch[]->s;
if(k==s+) return o->v;
else if(k<=s) return kth(o->ch[],k);
else return kth(o->ch[],k-s-);
} const int maxn=+;
int n,m;
int father[maxn],size[maxn]; int Find_Set(int x) {
if(father[x]!=x)
father[x] = Find_Set(father[x]);
return father[x];
} int main()
{
//freopen("in.txt","r",stdin);
root = NULL;
for(int i=;i<maxn;i++) {
father[i] = i;
size[i] = ;
}
scanf("%d%d",&n,&m);
//for(int i=0;i<n;i++)
//insert(root,1);
while(m--) {
int cmp;
scanf("%d",&cmp);
if(cmp==) {
int u,v;
scanf("%d%d",&u,&v);
int fx = Find_Set(u);
int fy = Find_Set(v);
if(fx!=fy)
{
if(size[fx]!=) remove(root,size[fx]);
if(size[fy]!=) remove(root,size[fy]);
father[fy] = fx;
size[fx]+=size[fy];
insert(root,size[fx]);
}
}
else {
int k;
scanf("%d",&k);
printf("%d\n",kth(root,k));
}
} return ;
}