这题也能够用树状数组做，并且树状数组姿势更加优美。代码更加少，只是这个Treap树就是求第K大元素的专家……所以速度比較快。

这个也是从那本红书上拿的模板……自己找了资料百度了好久，才理解这个Treap主要的知识，要是自己写真的得写到什么时候啊！。。

然后输入的时候是写n-k+1反着找的，就是这里又浪费了好多时间debug。唉……

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <list>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#define PI acos(-1.0)

#define mem(a,b) memset(a,b,sizeof(a))

#define sca(a) scanf("%d",&a)

#define sc(a,b) scanf("%d%d",&a,&b)

#define pri(a) printf("%d\n",a)

#define lson i<<1,l,mid

#define rson i<<1|1,mid+1,r

#define MM 440004

#define MN 1008

#define INF 100000007

#define eps 1e-7

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

struct Treap

{

    int root,treapCnt,key[MM],priority[MM],childs[MM][2],cnt[MM],size[MM];

    Treap()

    {

        root=0;

        treapCnt=1;

        priority[0]=INF;

        size[0]=0;

    }

    void update(int x)

    {

        size[x]=size[childs[x][0]]+cnt[x]+size[childs[x][1]];

    }

    void rotate(int &x,int t)

    {

        int y=childs[x][t];

        childs[x][t]=childs[y][1-t];

        childs[y][1-t]=x;

        update(x);

        update(y);

        x=y;

    }

    void _insert(int &x,int k)

    {

        if(x)

        {

            if(key[x]==k) cnt[x]++;

            else

            {

                int t=key[x]<k;

                _insert(childs[x][t],k);

                if(priority[childs[x][t]]<priority[x]) rotate(x,t);

            }

        }

        else

        {

            x=treapCnt++;

            key[x]=k;

            cnt[x]=1;

            priority[x]=rand();

            childs[x][0]=childs[x][1]=0;

        }

        update(x);

    }

    void _erase(int &x,int k)

    {

        if(key[x]==k)

        {

            if(cnt[x]>1) cnt[x]--;

            else

            {

                if(childs[x][0]==0&&childs[x][1]==0)

                {

                    x=0;

                    return ;

                }

                int t=priority[childs[x][0]]>priority[childs[x][1]];

                rotate(x,t);

                _erase(x,k);

            }

        }

        else _erase(childs[x][key[x]<k],k);

        update(x);

    }

    int _getkth(int &x,int k)

    {

        if(k<=size[childs[x][0]]) return _getkth(childs[x][0],k);

        k-=size[childs[x][0]]+cnt[x];

        if(k<=0) return key[x];

        return _getkth(childs[x][1],k);

    }

    void insert(int k)

    {

        _insert(root,k);

    }

    void erase(int k)

    {

        _erase(root,k);

    }

    int getkth(int k)

    {

        return _getkth(root,k);

    }

}treap;

int f[MM],a[MM];

int find(int x)

{

    return f[x]==x?x:f[x]=find(f[x]);

}

int main()

{

    int n,m,i,k,x,y;

    sc(n,m);

    for(i=0;i<=n;i++) f[i]=i,a[i]=1; //初始每一个区间的元素都是1咯。自身嘛。

    for(i=1;i<=n;i++) treap.insert(1);

    for(i=1;i<=m;i++)

    {

        sca(k);

        if(!k)

        {

            sc(x,y);

            x=find(x),y=find(y);

            if(x==y) continue;

            f[y]=x;

            treap.erase(a[x]); //先把这两个区间删除了

            treap.erase(a[y]);

            a[x]+=a[y];  //区间合并。元素相加

            treap.insert(a[x]); //然后把合并的加到treap平衡树中

            n--;  //合并区间，总区间少1

        }

        else

        {

            sca(k);

            pri(treap.getkth(n-k+1)); //反着找

        }

    }

    return 0;

}