【左偏树】【模板】

定义

首先定义一个点的dist为：
若该节点是外节点（即左儿子或右儿子为空），则dist=1，否则dist就等于左右儿子dist的较小值+1；
那么左偏树是一个堆的集合，而且满足对于任意一个点都有：右儿子的dist<=左儿子的dist

用途

支持O(log N)的时间复杂度内合并两个堆，其他操作的复杂度与普通的二叉堆相同

实现

1.存储形式
与普通二叉堆的堆式存储不同，左偏树采用与动态开点线段树和平衡树类似的存储方式：
建立一个结构体,左偏树必备的有：左右儿子（ls,rs），dist,key值(val),该节点所在堆的根节点(rt)。除此之外，在不影响左偏树的形态结构的前提下，可以支持对整棵树进行区间加，区间乘，维护相应的懒标记即可。

struct node{
	int val,ls,rs,d,rt;
}t[N];

2. 查询最值（也就是查找一个点所在堆的根节点）
   采用并查集查找的方法，用一个find函数：

int find(int x)
{
	return t[x].rt==x?x:t[x].rt=find(t[x].rt);
}

3. 合并操作
   左偏树的核心操作（设该树为小根堆）
   先比较两个堆根节点的大小，设较小的根节点为x，另一个为y。
   那么递归合并x的右子树与子树y。
   若合并后该节点不满足左偏树的性质：右儿子的dist<=左儿子的dist，则交换左右儿子。
   因为在递归的每一层都满足了左偏树的性质，因此，合并后的堆依然是个左偏树。
   又因为在递归中每次都用右子树，也就是dist较小的子树进行合并，所以复杂度是不超过O(log N)的。

int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(t[x].val>t[y].val||(t[x].val==t[y].val&&x>y)) swap(x,y);
	t[x].rs=merge(t[x].rs,y);//t[t[x].rs].rt=x;
	if(t[t[x].rs].d>t[t[x].ls].d) swap(t[x].ls,t[x].rs);
	t[x].d=t[t[x].rs].d+1;
	return x;
}

4. 删除操作
   若要删除一个堆的根节点，只需将根节点的左右儿子合并即可。
   但需要注意的是，因为根节点的维护是利用并查集维护的，因此，若要依然保持整棵树对根节点维护的正确性，不能仅仅把左右儿子的根节点指向合并后原树的根节点，还要把删除的点的根节点指向合并后原树的根节点。

t[fx].rt=t[t[fx].ls].rt=t[t[fx].rs].rt=merge(t[fx].ls,t[fx].rs);