自动搬运

查看原文

来自洛谷，原作者为

	山田リョウ この先どうなら楽ですか。

搬运于2025-08-24 22:05:47，当前版本为作者最后更新于2021-06-27 17:50:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大致就是要让你支持三个操作：

1. 把某个点的权值减小至 $0$
2. 把某个集合的最大值减小至某个值
3. 把某两个集合合并

明显用左偏树，不会的左转模板的题解区。

然后主要讨论该怎么减小权值，其实对于减小权值的这个点，可能需要调整的是他的儿子，因为他本来就比父亲小，然后减小后肯定还会比父亲小，但是儿子就比一定还比他小了，所以我们需要把他的两个儿子合并起来，再和整个堆重新合并一下。

但是我们发现了一个问题，因为把这个点的儿子拿走后他的 dist 也变了，所以我们需要往上调，可是树高是可以达到 $O(n)$ 的啊，其实我们可以直接暴力往上调，调到不能调为止，这样的复杂度还是 $O(\log_2 n)$ 的，因为这样调整的次数是结束调整时那个点的 dist，而树中任何一个点的 dist 都不会超过 $\log_2 n$。

但是本题稍稍有点问题，如果有两个罪恶值相等的坏事，题目没说怎么处理，所以如果你的左偏树写法和题解有区别的话，可能会过不了，于是我限定了一下，要求对于罪恶值相等的坏事，认为编号更小的更坏，在这里，顺便卡掉了没有路径压缩的并查集。

贴一份我的代码，写法较为奇怪，见谅。由于上面提到的原因导致过不了这道题，但是是可以过掉我重新造的数据的那道题。