P8985 [北大集训 2021] 魔塔 OL

Alex_Wei · 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 是值域。

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