【学习笔记】左偏树 / 可并堆

**模板** [P3377](https://www.luogu.org/problem/P3377) # 原理 **定义：** 若一个节点有儿子是空的，那么这个节点就叫空节点。而一个节点的$dis$值代表从这个节点出发，只经过右儿子到达一个空节点最少需要走的边数。 **左偏树** 的意思是：对于一棵树上的每一个节点，其左儿子的$dis$值大于等于右儿子的$dis$值，所以这棵树“向左偏”。 若以$u,v$为根的两个堆需要合并，由于已经维护好了左偏性质，所以只需要将$v$合并到$u$最右边的空节点，然后再递归维护左偏性质即可。 很显然，在最坏情况下，由于堆的性质，$dis[1]$到达$logn$，合并操作依然能够维持在$O(logn)$，是非常优秀的。 --- 代码： ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 10; int n, m, heap[MAXN]; int fa[MAXN], ls[MAXN], rs[MAXN], dis[MAXN]; bool del[MAXN]; int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } int Merge(int u, int v) { if (!u || !v) return u + v; if (heap[u] == heap[v] ? u > v : heap[u] > heap[v]) swap(u, v); // 题目描述提到：优先删除原序列中靠前的 rs[u] = Merge(rs[u], v); // 向右子树递归 if (dis[ls[u]] < dis[rs[u]]) swap(ls[u], rs[u]); // 维护左偏性质 fa[ls[u]] = fa[rs[u]] = fa[u] = u; // 更新父亲 dis[u] = dis[rs[u]] + 1; // 递归计算 dis 值 return u; } void pop(int u) { del[u] = true; fa[ls[u]] = ls[u]; fa[rs[u]] = rs[u]; // 先把左右儿子拆出去 fa[u] = Merge(ls[u], rs[u]); // 然后合并为一个新堆 } void init() { for (int i = 1; i <= n; i++) fa[i] = i; } int main() { dis[0] = -1; // 注意！此处是为了保证叶子节点 dis = 0 scanf("%d %d", &n, &m); init(); for (int i = 1; i <= n; i++) scanf("%d", &heap[i]); for (int opt, x, y; m; m--) { scanf("%d", &opt); if (opt == 1) { scanf("%d %d", &x, &y); if (del[x] || del[y]) continue; x = find(x), y = find(y); if (x != y) fa[x] = fa[y] = Merge(x, y); } else { scanf("%d", &x); if (del[x]) { printf("-1\n"); continue; } x = find(x); printf("%d\n", heap[x]); pop(x); } } return 0; } ```