因为也是昨天刚接触左偏树，从头理解，如有不慎之处，跪请指教。
左偏树：
什 么是（fzy说）左偏树啊？
前置知识：
左偏树中dist：表示到右叶点（就是一直往右下找，最后一个）的距离，特别的，无右节点的为0。
堆：左偏树是个堆。
关于左偏性质：可以帮助堆合并（研究深了我也不懂的，看代码理解）
对于任意的节点，dist[leftson]>=dist[rightson]，体现了左偏性质。
同理可得：对于任意右儿子的父亲节点的dist自然等于右儿子的dist+1喽
关于各种操作：
merge:
是插入操作的函数，具体步骤如下：
1.对于两个堆x，y，判断x，y是否为0，如果有一个为0，相当于没合并，直接返回另一个有元素的堆。
2.找到value值更大的那个堆头放到顶上，如果value值一样的话就按堆顶编号来排序。为了方便代码实现，我们可以规定x为符合条件（小，大跟堆）的那个堆头，然后如果y符合条件就交换x，y值。
3.既然堆头找着了，就可以进一步的合并堆头右儿子和y堆了（为了尽量保证左偏的性质）。如此递归下去，随着新堆头被一次次确定，最终这个堆会被一点一点融合到另一个堆中。
4.但是，鉴于合成完后，不一定能够保证左子树的dist值一定会比右字数的大，我们只要判断一下是否符合左偏性质，如果不符合，就交换一下当前节点左右子树就行了。因为是递归执行，从更深节点一层一层上来，那么必然的整个堆会符合左偏性质。然后更新一下dist为右子树dist+1.一次merge完成。
代码：
inline int merge(int x, int y)
{
if(!x||!y)return x+y;
if(tree[x].value>tree[y].value||(tree[x].value==tree[y].value&&x>y))swap(x,y);
rs=merge(rs,y);
if(tree[ls].dist<tree[rs].dist)swap(ls, rs);tree[ls].rt=tree[rs].rt=tree[x].rt=x,tree[x].dist=tree[rs].dist+;
//更新dist
return x ;
}
2.pop弹出函数：
弹出函数，即弹出堆顶。方法很简单：没有了堆顶，整个左偏树就被分为了两个小的左偏树。我们只要忽略掉堆顶合并（merge）两个小的左偏树即可。
注意事项：不要忘了堆顶元素相关信息还原为初始。
代码：
inline void pop(int x)//弹出x为堆顶的堆
{
tree[x].value=-,tree[ls].rt=ls,tree[rs].rt=rs;
tree[x].rt=merge(ls,rs);
}
3.get函数：
没啥可说的，就是并查集找父亲并且路径压缩。
代码：
int get(int x)
{
return x==tree[x].rt?x:tree[x].rt=get(tree[x].rt);
}
三个函数代码已经完结。
main函数内根据题意进行模拟即可。
总代码：
#include<queue>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define N 100003
#define ls tree[x].son[0]
#define rs tree[x].son[1]
using namespace std;
int read()
{
int ans=;
char ch=getchar(),last=' ';
while(ch<''||ch>'')last=ch,ch=getchar();
while(ch>=''&&ch<='')ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
return last=='-'?-ans:ans;
}
inline void swap(int &x,int &y)
{
x^=y^=x^=y;
}
int n,num,hea[N],t,judge,b,c;
struct tre{
int son[],rt,dist,value;
}tree[N];
inline int merge(int x, int y)
{
if(!x||!y)return x+y;
if(tree[x].value>tree[y].value||(tree[x].value==tree[y].value&&x>y))swap(x,y);
rs=merge(rs,y);
if(tree[ls].dist<tree[rs].dist)swap(ls, rs);tree[ls].rt=tree[rs].rt=tree[x].rt=x,tree[x].dist=tree[rs].dist+;
//更新dist
return x ;
}
int get(int x)
{
return x==tree[x].rt?x:tree[x].rt=get(tree[x].rt);
}
inline void pop(int x)//弹出x为堆顶的堆
{
tree[x].value=-,tree[ls].rt=ls,tree[rs].rt=rs;
tree[x].rt=merge(ls,rs);
}
int main(){
n=read(),t=read();tree[].dist=-;
for (int i=;i<=n;i++)
tree[i].rt=i,scanf("%d",&tree[i].value);//并差集初始化+输入
for (int i=;i<=t;i++){
judge=read(),b=read();
if (judge==){
c=read();
if (tree[b].value==-||tree[c].value==-) continue ;
int f1=get(b),f2=get(c);if(f1!=f2)tree[f1].rt=tree[f2].rt=merge(f1,f2);//合并操作
}
else {
if(tree[b].value==-)printf("-1\n") ;
else printf("%d\n",tree[get(b)].value),pop(get(b)) ;//输出并弹出
}
}
return ;
}
完结。
彩蛋：有趣的东西：
极度真实的左偏树。
来自dalao