题解 P11983 [JOIST 2025] 展览会 3 / Exhibition 3

· · 题解

参考了 链接 中 \text{Flamire} 的题解。

本题解的复杂度分析中认为 n,m 同阶。

考虑暴力怎么做。
对于值 v，设其在 A 中出现了 cnt_v 次。对于一个区间集合 S，设 f(S) 表示可以覆盖 S 中所有区间的点的个数的最小值。f(S) 可以通过一个简单的贪心求得：将所有区间按 r_i 排序，然后贪心的在 r_i 处加入点即可。从大到小枚举值域，从小到大枚举区间编号 i，如果 f(S\cup\{(l_i,r_i)\})\le cnt_v，那么把 b_i 赋为 v，将 (l_i,r_i) 加入 S，然后把区间 (l_i,r_i) 删除。暴力复杂度为 O(n^3)。

尝试优化上述暴力。注意到我们求 f(S) 的贪心事实上可以求出第 i 个点可能的最大值。同理，从大到小按 l_i 排序也可以求出其最小值，不妨分别设为 sr_i 和 sl_i。所以 f(S)=f(S\cup\{(l_i,r_i)\}) 当且仅当存在 k 使得 [sl_k,sr_k] 与 [l_i,r_i] 相交。对于每个值，先二分出其可以覆盖的最长前缀，然后逐个检查每个区间是否可以加入 S，加入后重构 sl 和 sr。因为每个区间只会造成一次重构，可以得到一个 O(n^2\log n) 的做法。

发现第一部分的二分可以通过先进行倍增来优化。先找到最小的 k 使得覆盖的前缀的长度小于 2^k，然后在 [2^{k-1},2^k) 内二分。这样因为二分的区间长度和删去的区间长度同阶，第一部分的复杂度均摊 O(n\log^2 n)。可以通过提前对长为 2^i 的前缀排序做到 O(n\log n)。

对于第二部分，注意到插入区间的过程中 sl 单增，sr 单减，且 sl_i 不会超过 sl_{i+1}，而 sl_i 只有 |S| 个合法位置（sr 同理），所以 sl 和 sr 的变化量是 O(|S|) 级别的。只需要在每次插入区间时找到对应的 sl 和 sr 然后暴力更新直到某个位置 sl 或 sr 不再发生变化。

现在的复杂度瓶颈在于对于每个值 v，找到编号最小的 [l_i,r_i] 使得其和某一个 [sl_k,sr_k] 相交。一个暴力的想法是对于每个 [sl_k,sr_k] 维护编号最小的与其相交的 [l_i,r_i]。但是存在一个问题：一个区间 [l_i,r_i] 可以包含很多个 [sl_k,sr_k]，那么在 [l_i,r_i] 被使用后需要更新很多个 [sl_k,sr_k] 对应的编号，所以复杂度是假的。考虑优化，注意到若存在 [sl_k,sr_k] 被 [l_i,r_i] 包含，那么 [l_i,r_i] 一定会被加入。在处理满足上述条件的 [l_i,r_i] 后，每个 [l_i,r_i] 只会对至多两个 [sl_k,sr_k] 有贡献，所以复杂度正确。这时求最小编号可以用线段树维护（[l_i,r_i] 与 [sl_k,sr_k] 相交当且仅当 l_i 或 r_i 在 [sl_k,sr_k] 内）。注意更新每次 [sl_k,sr_k] 后需要加入新的包含其的 [l_i,r_i]。

综上，复杂度可以做到 O(n\log n)。

代码，偷懒写的 O(n\log^2n)。