左偏树是一类拥有下列操作的数据结构：
插入一个数 \(O(log n)\)
求最小值 \(O(1)\)
(资料图片仅供参考)删除一个节点 \(O(log n)\)
合并两棵树 \(O(log n)\)
左偏树本身具有堆的性质，又称为可并堆。
以维护最小值为例：
概念：
权值\(val\)
距离\(dis\)：到最近的根节点的距离 （\(\leqslant log n\)）
\(left\rightarrow dist\rightarrow right\rightarrow dist\)
\(f[k]\)：距离为\(k\)的子树，至少包含多少个点。
- \(f[k]\geqslant 2^k-1\)证明：\(k=1,n=k-1\)\(n=k, f(n)\geqslant 2^{k-1}-1+2^{k-1}-1+1=2^k-1\)故必须要有\(f[k]\geqslant 2^k-1\)
\(merge(a,b)\)：合并子树\(a,b\)，并返回合并后的根节点。比较\(a,b\)的根节点的大小，如果\(a\)的根节点小于\(b\)的根节点，则把\(b\)插到\(a\)的右子树，然后检查\(a\)是否符合左偏性质，如果不满足就把左右子树交换。这个操作存\(root\)时需要路径压缩。为什么可以用并查集？ 只有合并而没有分裂。
于是下面的操作就很简单了。
插入操作：建立只包含一个点的左偏树，将其与原树合并。最小值：根节点删除操作：合并左右子树。
code
bool cmp(int x, int y){ if (v[x] != v[y]) return v[x] < v[y]; return x < y;}int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x];}int merge(int x, int y){ if (!x || !y) return x + y; if (cmp(y, x)) swap(x, y); r[x] = merge(r[x], y); if (dist[r[x]] > dist[l[x]]) swap(l[x], r[x]); dist[x] = dist[r[x]] + 1; return x;}习题选做：P4359 【CQOI2016】 伪光滑数P3261 【JLOI2015】 城池攻占
