左偏树（Leftist Tree）
定义
外节点：只有一个儿子或没有儿子的节点。
距离：一个节点到离他最近的外节点的距离，即两节点之间的路径权值和。特别地，外节点的距离为 \(0\)，空节点的距离为 \(-1\).
左偏树：满足如下性质的二叉树：
- 堆性质：任何节点的权值小于等于儿子节点的权值，即 \(val_{fa_i} \le val_i\).
- 左偏性质：任何节点的左儿子距离大于等于右儿子距离，即 \(d_{ls_i} \ge d_{rs_i}\).
推论：
- 任意节点的距离等于右儿子距离 \(+ 1\)，即 \(d_i = d_{rs_i} + 1\).
- 根节点的距离为 \(d\) 的左偏树，节点数不少于 \(2^{d+1} - 1\).
操作
合并（Merge）
合并根节点为 \(x, y\) 的两颗左偏树。
- 假设 \(val_x \le val_y\)，那么根节点一定为 \(x\)，否则为 \(y\).
- 需要递归合并 \(rs_x\) 和 \(y\)，并将新树的根作为 \(rs_x\).
- 合并完成后，\(d_{rs_x}\) 可能会变，为了保证左偏性质，若 \(d_{ls_x} < d_{rs_x}\)，那么交换 \(x\) 的左右儿子。
- 更新 \(d_x\)，以 \(x\) 为合并后的根节点。
int merge(int x, int y)
{
if(!x || !y) return x + y; // 若一个堆为空则返回另一个堆
if(val[x] > val[y]) swap(x, y); // 取值较小的作为根，满足堆性质
r[x] = merge(r[x], y), fa[r[x]] = x; // 递归合并右儿子与另一个堆
if(dis[l[x]] < dis[r[x]]) swap(l[x], r[x]); // 若不满足左偏性质则交换左右儿子
dis[x] = dis[r[x]] + 1;
return x;
}
插入（Push）
合并一个只有一个节点的左偏树。
弹出（Pop）
- 将根的左右节点合并，然后将合并后的节点设为根。
int pop(int x)
{
int ls = l[x], rs = r[x];
int y = merge(ls, rs);
fa[y] = 0;
return y;
}
删除（Del）
- 将左右儿子合并后挂到父节点下，若父节点不满足左偏性质，则一路调整。
建树（Build）
- 暴力插入时间复杂度为 \(O\left(n \log n\right)\).
- 利用队列优化，两个两个合并，时间复杂度 \(O(n)\).