自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:44:20，当前版本为作者最后更新于2023-02-13 12:30:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

D1T2. P8985 [北大集训 2021] 魔塔 OL

问题的一个子问题是经典的贪心：Monster Hunter，以下记作 MH。它的解法是：对于 $a_i\leq b_i$，我们放到前半部分，并按 $a_i$ 从小到大排序；对于 $a_i > b_i$，我们放到后半部分，并按 $b_i$ 从大到小排序。算法正确性可通过邻项交换（Exchange Arguments）证明，相当于比较 $\max(a_1, a_1 - b_1 + a_2)$ 和 $\max(a_2, a_2 - b_2 + a_1)$，较小的排在前面。

回到原问题。容易看出这是对四维偏序内的所有点求 MH，看起来非常阴间。一般的数据结构肯定寄了，时间复杂度太高，我们只能考虑一些奇技淫巧。

对于高维偏序，有个神奇的做法，就是对每一维的所有值域前缀，用 bitset 处理出落在这个前缀内的所有点的标号，那么一次查询相当于将每个维度对应的 bitset 求交，时空复杂度均为 $\mathcal{O}(\frac{n ^ 2k} w)$。

对于按顺序处理的信息，我们真的只能一个个处理吗？答案是否定的。有个神奇的做法：按 $B = \log_2 n$ 分块，预处理块内所有 $2 ^ B$ 个集合的信息。对于每个询问，只要能快速求出落在该块内的所有点的集合，就可以给总复杂度除掉一个 $\log_2 n$。

结合上述两个技巧，我们得到如下做法：每次处理 $B = \log_2 n$ 个元素。DP 求出 $2 ^ B$ 个集合的信息。然后对于每一维限制，预处理值域的每个前缀的点的集合，用 $B$ 位二进制数描述。最后依次处理所有询问即可。时间复杂度是 $\mathcal{O}(\frac {(n + q + V) n}{\log n})$，其中 $V$ 是值域。

常数优化：注意编号维度大小很大。我们考虑扫描线，先对加入或删除块内每个点的事件按编号排序，然后按编号顺序处理询问，并用指针维护该维度的限制即可。代码。