堆

参考资料

• 堆简介 - OI Wiki

std::priority_queue

37 Bcpp

std::priority_queue<pair<int,int>> q;

__gnu_pbds::priority_queue

120 Bcpp

#include <bits/extc++.h>
using namespace __gnu_pbds;
__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int>>> q;

左偏树

273 Bcpp

struct Node
{
	int val,ls,rs,dis;
}t[N];
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))swap(x,y);
	t[x].rs=merge(t[x].rs,y);
	if(t[t[x].ls].dis<t[t[x].rs].dis)swap(t[x].ls,t[x].rs);
	t[x].dis=t[t[x].rs].dis+1;
	return x;
}

例题

洛谷 P3378 【模板】堆

给定一个数列，初始为空，请支持下面三种操作：

1. 给定一个整数 $x$，请将 $x$ 加入到数列中。
2. 输出数列中最小的数。
3. 删除数列中最小的数（如果有多个数最小，只删除 $1$ 个）。

洛谷 P3377 【模板】左偏树/可并堆

有 $n$ 个小根堆，每个堆包含一个数。需要支持两种操作：

1. 1 x y：将第 $x$ 个数和第 $y$ 个数所在的小根堆合并（若 $x$ 或 $y$ 已经被删除或 $x$ 和 $y$ 在同一个堆内，则无视此操作）。
2. 2 x：输出第 $x$ 个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第 $x$ 个数已经被删除，则输出 -1 并无视删除操作）。

洛谷 P11266 【模板】可并堆 2

给定正整数 $n$ 和 $m$ 以及一个长为 $n$ 的整数序列 $a_{1,\dots,n}$。

你需要维护序列 $a_{1,\dots,n}$ 以及 $n$ 个集合 $S_{1,\dots,n}$，初始时 $S_i=\{i\}$。

接下来要进行以下四种操作共 $m$ 次，每次操作形如：

• 0 x y：表示将元素 $y$ 从集合 $S_x$ 中删去。保证此时元素 $y$ 在集合 $S_x$ 中。
• 1 x：表示询问 $\min_{i\in S_x} a_i$，保证此时集合 $S_x$ 非空。
• 2 x y：将集合 $S_y$ 中并入 $S_x$ 并清空集合 $S_y$。保证此时集合 $S_x,S_y$ 均非空，且此次操作后不会再出现涉及集合 $S_y$ 的操作。
• 3 x y z：表示将 $a_y$ 赋值为 $z$。保证此时元素 $y$ 在集合 $S_x$ 中，且 $z<a_y$。

不难发现这是一道堆的模板题，所以现在请你完成它。

洛谷 P2713 罗马游戏

罗马皇帝的军队 $n$ 个士兵，每个士兵都是一个独立的团，每个士兵都有一个分数。

皇帝很喜欢平面几何，他对那些得分很低的士兵嗤之以鼻。

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

• M i j：把 $i$ 所在的团和 $j$ 所在的团合并成一个团。如果 $i,j$ 有一个士兵是死人，那么就忽略该命令。
• K i：把 $i$ 所在的团里面得分最低的士兵杀死。如果 $i$ 这个士兵已经死了，这条命令就忽略。

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

保证士兵的分数互不相同。

洛谷 P1456 Monkey King

曾经在一个森林中居住着 $N$ 只好斗的猴子。在最初他们我行我素，互不认识。但是猴子们不能避免争吵，且两只猴子只会在不认识对方时发生争吵，当争吵发生时，双方会邀请它们各自最强壮的朋友并发起决斗（决斗的为各自最强壮的朋友）。当然，在决斗之后两只猴子和他们各自的伙伴都认识对方了（成为朋友），虽然他们曾经有过冲突，但是他们之间绝不会再发生争吵了。

假设每只猴子有一个强壮值，强壮值将在一场决斗后减少为原先的一半（例如 $10$ 会减少到 $5$，而 $5$ 会减少到 $2$，即向下取整）。

我们也假设每只猴子都认识它自己（是自己的朋友）。即当他是他朋友中最强壮的，他自己就会去决斗。

洛谷 P10641 BZOJ3252 攻略

给定一个有 $n$ 个结点的树，树有点权且点权为正整数。现选取 $k$ 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。