P4971 断罪者 题解

· · 题解

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

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

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

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

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

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

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