【题解】右偏树

大家好，题解里很多大佬都是写的左偏树。 我很沙雕，所以我就来讲讲$\Huge\text{右}$偏树。  ~~上面就是一棵右偏树（误）~~ # 原理 **定义：** 若一个节点有儿子是空的，那么这个节点就叫空节点。而一个节点的 $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); // 题目描述提到：优先删除原序列中靠前的 ls[u] = Merge(ls[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[ls[u]] + 1; 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(find(x)); } } return 0; } ``` 如果你想看正经的左偏树该怎么写，也可以 [看这里](https://ncc79601.blog.luogu.org/leftist-tree)，~~你会发现怎么偏都没什么关系~~