吐槽：CSDN有什么毛病，题面里出现了杀|人都过不了审核。

前言

树不是从来都讲究平衡的么？怎么，还要故意偏？

引入

【BZOJ1455】罗马游戏

罗马皇帝很喜欢玩杀|人游戏。 他的军队里面有n个人，每个人都是一个独立的团。最近举行了一次平面几何测试，每个人都得到了一个分数。 皇帝很喜欢平面几何，他对那些得分很低的人嗤之以鼻。

他决定玩这样一个游戏。 它可以发两种命令：

1.Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人，那么就忽略该命令。

2.Kill(i)。把i所在的团里面得分最低的人杀|死。如果i这个人已经死了，这条命令就忽略。

皇帝希望他每发布一条kill命令，下面的将军就把被杀的人的分数报上来。（如果这条命令被忽略，那么就报0分）

堆的合并

已经想到堆了吧……没错，基本算法就是堆，但是我们还要支持堆的合并。

堆的合并？不是很简单？暴力启发式合并即可。

然而，我们有更优秀的合并方法，还能同时维护多个性质。

先看一下定义吧。

算法定义

左偏树是一种可并堆的实现。左偏树是一棵二叉树，它的节点除了和二叉树的节点一样具有左右子树指针（left, right）外，还有两个属性： 键值和距离（英文文献中称为s-value）。键值用于比较节点的大小。

距离的定义：

当且仅当节点 i 的左子树且右子树为空时，节点被称作外节点（实际上保存在二叉树中的节点都是内节点，外节点是逻辑上存在而无需保存。把一颗二叉树补上全部的外节点，则称为extended binary tree）。节点i的距离是节点 i 到它的后代中的最近的外节点所经过的边数。特别的，如果节点 i 本身是外节点，则它的距离为0;而空节点的距离规定为 -1。

所以左偏是用来干嘛的？用来快速合并的！

我们把一个东西记作dis，空节点默认dis=0，非空节点为disi=min(disls,disrs)+1（就是说左右儿子里面取较小）。要维护左偏的性质，就要保证disls>=disrs，这样一来，就有disi=disrs+1。

在我们合并两个堆的时候，我们考虑哪个堆的堆顶元素会作为新堆的堆顶元素。显然是键值较大的那一个。那么我们就，把较大的作为堆顶，然后，把另一个堆跟堆顶的右儿子进行合并！合并的过程是递归的，可以证明复杂度为O(logn)。

代码

#include<bits/stdc++.h>#define ls t[x].ch[0]#define rs t[x].ch[1]using namespace std;const int N=1000010;struct node {int rt, dis, val, ch[2];}t[N];int n, m;int Get(int x) {return t[x].rt==x? x: t[x].rt=Get(t[x].rt);}inline void sw_swap(int &x, int &y) {x^=y^=x^=y;}inline 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)) sw_swap(x, y);rs=Merge(rs, y);if (t[ls].dis<t[rs].dis) sw_swap(ls, rs);t[ls].rt=t[rs].rt=t[x].rt=x, t[x].dis=t[rs].dis+1;return x;}inline void Pop(int x) {t[x].val=-1, t[ls].rt=ls, t[rs].rt=rs, t[x].rt=Merge(ls, rs);}int main() {scanf("%d", &n);t[0].dis=-1;for(int i=1; i<=n; i++) t[i].rt=i, scanf("%d", &t[i].val);scanf("%d", &m);for(int i=1; i<=m; i++) {int x, y; char ch=getchar();while(ch!='K'&&ch!='M') ch=getchar();if(ch=='M') {scanf("%d%d", &x, &y);if(t[x].val==-1||t[y].val==-1) continue;int f1=Get(x), f2=Get(y);if(f1!=f2)t[f1].rt=t[f2].rt=Merge(f1, f2);} else {scanf("%d", &x);if(t[x].val == -1) printf("0\n") ;else printf("%d\n", t[Get(x)].val), Pop(Get(x)) ;}}}

如果觉得《左偏树 学习笔记》对你有帮助，请点赞、收藏，并留下你的观点哦！