<h1>定义</h1>

大家都知道优先队列吧。
有时候我们需要合并优先队列，反正我们不能重新插入吧，我们就需要一种神奇的数据结构--可并堆

可并堆可以支持在$O(NlogN)$下进行插入，删除，合并，求极值。
在OI选手中，实现可并堆的最好方法是左偏树
那么左偏树是递归定义的，它与二叉堆不同，他不是一棵完全二叉树。
左偏树中的重要定义是NPL-表示该结点到最近的外部结点的位置。
满足要求 堆的要求+做结点的NPL一定不小于有结点的NPL
得到$ NPL(i) = NPL(i.right) + 1 $ $ max{NPL} &lt; log(N+1) $
现在我们可以发现，这个堆大部分时候是向左偏的，所以说保证复杂度的是它的右链，所以所有操作 都被放到右链上 。

<h1>操作</h1>

对于小根堆H1和H2的合并（小根堆）
如果$ H1==NULL $或$ H2==NULL $那就$ return H1+H2 $
对于合并后的$ H1 $，如果左右子树的$ Npl $破坏规则，直接交换左右子树
以上反之亦然
注意一下找父亲过程要路径压缩一下，不然会被卡成 $O(n)$。

<h1>代码</h1>

左偏树（可并堆）

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define lc (chx)
#define se second
#define U unsigned
#define rc (chx)
#define Re register
#define LL long long
#define MP std::make_pair
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100000+5;
int chMAXN,dis[MAXN],sonMAXN,f[MAXN],val[MAXN];

inline int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

inline int merge(int x,int y){
    if(!x || !y) return x + y;
    if(val[x] > val[y] || (val[x] == val[y] && x > y)) std::swap(x,y);
    rc = merge(rc,y);if(dis[lc] < dis[rc]) std::swap(lc,rc);
    f[lc] = f[rc] = f[x] = x;dis[x] = dis[rc] + 1;return x;
}

inline void del(int x){
    val[x] = -1;f[lc] = lc;f[rc] = rc;
    f[x] = merge(lc,rc);
}

int N,M;

int main(){
    scanf("%d%d",&N,&M);dis[0] = -1;
    FOR(i,1,N) f[i] = i,scanf("%d",val+i);
    while(M--){
        int opt,x,y;scanf("%d%d",&opt,&x);
        // DEBUG(M);
        if(opt == 1){
            scanf("%d",&y);
            if(val[x] == -1 || val[y] == -1) continue;
            int fx = find(x),fy = find(y);
            if(fx != fy) f[fx] = f[fy] = merge(fx,fy);
        }
        else{
            if(val[x] == -1) puts("-1");
            else printf("%dn",val[find(x)]),del(find(x));
        }
    }
    return 0;
}