[SCOI2011] 植物大战僵尸 + 减半警报器

_Diu_ · 2024-05-30 16:29:26 · 个人记录

关于这个题，想到了一个加强思路。

快进到每个点拆成两个，维护若干平衡树。然后我们把每一行第一个位置丢到一个堆里面，每次取出第一个然后把对应平衡树上的后缀的点做点权减（点权指出现次数）。删除点变成 swap 两个平衡树。

然后我们注意到对于后缀点权减的操作我们是暴力做的，具体来说是以 O(\log n) 的时间使一个点的点权 -1，非常垃圾，但是因为 \sum val=m 所以是对的。

这部分是容易优化的，具体来说，考虑 lxl 提出的减半警报器，对于一个点权为 k，如果它要被删空，那么他拆出来的两个点至少要有一个被删 \lceil \frac k2\rceil 次。那我们给拆出来的两个点都赋上 \lceil \frac k2\rceil 的点权，如果被清空了我们就标记成疑似被删除。对于疑似被删除的点我们花 O(\log n) 的时间找到对应平衡树的对应信息，如果被删除就做后续操作，否则就重新分配点权。这样每个点最多被标记疑似删除 O(\log V) 次。

如果点数为 n，操作量为 m，值域为 V，那么本题复杂度可以做到 O(n\log n\log V+m\log n)。为了使值域的优势体现出来，我们可以把操作变成输入给出在某个位置操作 k 次的形式，为了体现平衡树的优势，也可以增加单点刷新僵尸的操作（当然 swap 后缀已经很能体现平衡树的优势了）。