前言
要维护一段区间内的最值时，我们可以用堆（平衡树）来操作。
但是，如果要合并两个堆，复杂度就极高了。
所以，我们就要使用左偏树这个神奇的数据结构，来实现堆的合并。
引子 左偏树是什么？
左偏树是什么？
当然是向左偏的树。（废话）
实际上，现在来解释左偏树的概念还是有点难的，所以我们要先来看一些定义。
与左偏树相关的一些定义
外节点
外节点，顾名思义，就是在外部的节点。
它的定义是有至少一个子节点是空节点的节点是外节点。
注意是至少一个，而不是全部，不然就变成叶节点了。
而记录外节点有什么用呢？
当我们需要插入一个节点时，如果找到了外节点，就可以轻松将其插入到这个外节点的某一空子节点。
距离
左偏树一个很重要的概念就是节点的距离，我们可以将其记作(Dis(x))。
比较简单，一个节点的距离指的就是它到离它最近的外节点的距离。
对于该节点本身是外节点和该节点是空节点两种特殊情况，我们分别规定它们的距离为(0)和(-1)。
左偏树的一些性质
首先，我们要知道，左偏树是满足堆性质的（废话，它就是用来实现堆合并的）。
而左偏树另一比较重要的性质是左偏性。
让我们回到前面的那个问题，什么是左偏树？
现在我们可以对它进行解释了：对于左偏树中的任意一个节点，我们必须满足(Dis(LeftSon)ge Dis(RightSon))，即左儿子离外节点的距离必须大于等于右儿子离外节点的距离。
而这就是左偏树的左偏性了。
左偏树其实还有一个比较重要的性质，这个性质在上传信息的操作中起到了重要的作用：对于左偏树中的任意一个节点，(Dis(x)=Dis(RightSon)+1)。
证明： 根据左偏性，可以得到(Dis(RightSon)le Dis(LeftSon))，而左偏树中距离的定义是一个节点到离其最近的外节点的距离，故为(Dis(RightSon)+1)。
关于左偏树的合并操作
左偏树的核心操作就是它的合并（毕竟其他操作堆都能轻松实现）。
假设我们要合并两个根节点分别为(x)和(y)的左偏树。
首先，我们要判断(x)与(y)中是否存在空节点，如果有，可以直接退出函数。
然后，我们要比较权值大小（假设是小根堆），如果(Val_x>Val_y)，则交换(x)和(y)（维护堆性质）。
接下来，我们要将(x)的右儿子取出，与(y)进行合并，然后将合并后得到的根作为(x)新的右儿子。
为什么要选右儿子？
因为左偏树的左偏性啊！
也就是说，选右儿子，可以更早找到空节点将另一棵左偏树插入。
这就保证了左偏树合并操作的时间复杂度。
要注意的是，在合并后，右儿子的距离可能会小于左儿子，此时就需要交换左右儿子，从而维护左偏性。
代码如下：
inline int Merge(int x,int y)//将根节点为x和y的两棵左偏树合并
{
if(!x||!y) return x+y;//如果存在空节点，直接退出函数
if(node[x].Val>node[y].Val) swap(x,y);//比较权值大小，维护堆性质
if(node[node[x].Son[1]=Merge(node[x].Son[1],y)].Father=x,node[node[x].Son[0]].Dis<node[node[x].Son[1]].Dis) swap(node[x].Son[0],node[x].Son[1]);//将x的右儿子取出与y进行合并，然后比较左右儿子距离，维护左偏性
return node[x].Dis=node[node[x].Son[1]].Dis+1,x;//更新距离，返回合并后的根节点x
}
关于左偏树的其他操作
理解了合并，左偏树的其他操作就很简单了。
-
删除
删除操作，其实就是合并被删除节点的两个子树。代码如下：
inline void PopTop(int x)//弹出堆顶
{
if(!node[x=TopPos(x)].Exist) return;//如果堆顶不存在，退出函数
node[x].Val=node[x].Dis=-1,node[x].Exist=0,node[node[x].Son[0]].Father=node[node[x].Son[1]].Father=0,//清空信息
Merge(node[x].Son[0],node[x].Son[1]);//合并两棵子树
}
-
求堆顶元素值
我们可以对每一个节点记录它的(Father)，然后不断往上跳即可。代码如下：
inline int TopPos(int x) {while(node[x].Father) x=node[x].Father;return x;}//求出堆顶元素的编号
inline int TopVal(int x) {return node[TopPos(x)].Val;}//求出堆顶元素的值
模版题：【洛谷3377】【模板】左偏树（可并堆）
到这里，其实左偏树讲得也差不多了。
相信大家都发现了，左偏树也没有想象中那么难。
下面以这道模板题为例，贴一份完整代码：
#include<bits/stdc++.h>
#define N 100000
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
int n,a[N+5];
class FIO
{
private:
#define Fsize 100000
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)
#define pc(ch) (void)(FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,Fsize,stdout),Fout[(FoutSize=0)++]=ch))
int Top,FoutSize;char ch,*A,*B,Fin[Fsize],Fout[Fsize],Stack[Fsize];
public:
inline void read(int &x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}
inline void write(int x) {if(!x) return pc('0');if(x<0) pc('-'),x=-x;while(x) Stack[++Top]=x%10+48,x/=10;while(Top) pc(Stack[Top--]);}
inline void write_char(char x) {pc(x);}
inline void clear() {fwrite(Fout,1,FoutSize,stdout);}
}F;
class Class_LeftistTree
{
private:
struct Tree
{
int Val,Dis,Father,Exist,Son[2];
Tree(int x=0):Val(x){Dis=Father=Son[0]=Son[1]=0,Exist=1;}
}node[N+5];
inline int Merge(int x,int y)
{
if(!x||!y) return x+y;
if(node[x].Val>node[y].Val||(node[x].Val==node[y].Val&&x>y)) swap(x,y);
if(node[node[x].Son[1]=Merge(node[x].Son[1],y)].Father=x,node[node[x].Son[0]].Dis<node[node[x].Son[1]].Dis) swap(node[x].Son[0],node[x].Son[1]);
return node[x].Dis=node[node[x].Son[1]].Dis+1,x;
}
inline int TopPos(int x) {while(node[x].Father) x=node[x].Father;return x;}
public:
Class_LeftistTree() {node[0].Dis=-1,node[0].Exist=0;}
inline void Init(int n,int *data) {for(register int i=1;i<=n;++i) node[i]=Tree(data[i]);}
inline void Union(int x,int y) {if((x=TopPos(x))^(y=TopPos(y))&&node[x].Exist&&node[y].Exist) Merge(x,y);}
inline void PopTop(int x) {if(node[x=TopPos(x)].Exist) node[x].Val=node[x].Dis=-1,node[x].Exist=0,node[node[x].Son[0]].Father=node[node[x].Son[1]].Father=0,Merge(node[x].Son[0],node[x].Son[1]);}
inline int TopVal(int x) {return node[TopPos(x)].Val;}
}LeftistTree;
int main()
{
register int i,Q,op,x,y;
for(F.read(n),F.read(Q),i=1;i<=n;++i) F.read(a[i]);
for(LeftistTree.Init(n,a);Q;--Q)
{
if(F.read(op),F.read(x),op^1) F.write(LeftistTree.TopVal(x)),F.write_char('
'),LeftistTree.PopTop(x);
else F.read(y),LeftistTree.Union(x,y);
}
return F.clear(),0;
}
关于例题
有两道比较好的左偏树例题：
【BZOJ2809】【APIO2012】dispatching：这应该是比较裸的模板题，适合刚学左偏树的人练手。
【BZOJ4003】【JLOI2015】城池攻占：这道题就有一定的扩展了，需要在左偏树上加上懒惰标记，也是挺有意思的题目。