题面 APIO2012 派遣 Solution 这是一道左偏树的模板题，不会左偏树的可以戳这里 显然，我们可以发现对于同一颗子树，我们想让取的人尽可能便宜，如果说目前为止取的价格超过$C$,就优先把贵的人先丢掉。 因此，我们考虑用左偏树来维护这个东西。对于每一个人，我们都建一颗以价格为关键字的大根堆。考虑从下往上合并，一旦堆的元素总和超过$C$就不断弹栈，弹到合法为止。然后我们算一下$l_i*sum$，取个最大值就好。 时间复杂度$O(nlogn)$ 就酱，我们就可以把这道题切掉啦(ﾉﾟ∀ﾟ)ﾉ Code //Lu…

题面 洛谷P1110 Solution 我们看到这道题，我们不妨想把处于同一个点的骑士全部丢到一个小根堆左偏树里面。这样子，我们从下往上合并，合并完就去检查一下根是否满足当前城市的要求，一直弹根弹到满足要求为止。 至于能力的变化，这里的操作要求无外乎乘法和加法。因此，我们可以像线段树II那道题那样做两个标记，处理一下即可。每次合并、弹根之前都pushdown标记。 就酱，这题就被我们切掉啦~(*´ﾟ∀ﾟ｀)ﾉ 时间复杂度$O(nlogm)$ Code 数据生成器 #include<iostream> #…

为什么要学左偏树 有时候，某些题目要求我们合并两个堆。 合并两个堆，大家都知道可以用splay暴力启发式合并处理。很不幸的是，这玩意的复杂度是$O(nlog^2n)$的，在一些毒瘤题目专门考可并堆的题目中，是注定要被卡的。 可并堆系列算法可以很优雅的解决这系列的算法，她们可以在$O(nlogn)$的时间内处理两个堆合并的问题。而我现在要讲的左偏树就是可并堆中的一种。 什么是左偏树 正如她字面意思一样，是一颗向左“偏”的树。什么叫“向左偏”呢？我们知道，平衡树的时间复杂度比二叉查找树优秀，是因为平衡树的左右子树深度尽…