P11983 Solution

· · 题解

O：今天我们来做 P11983 [JOIST 2025] 展览会 吧。派对的时候，大家都说这个题是好题。

有一个序列 a_1, \ldots, a_n，请任意重排之，令 b_i = \max(a_{l_i}, \ldots, a_{r_i})，最大化 b_1, \ldots, b_m 的字典序。1 \leq a_i \leq n \leq 10^5，1 \leq m \leq 10^5。3 秒 / 1 GB。

C：看完这个题之后，我能提出一些简单的想法，比如说 O(n^2m)......只需要依次枚举每个区间对应的权值并判断即可，但是，这太暴力了，而且很难再优化了。

O：有一个部分分 a_i = i 看起来很有意思。如果每种数只出现一次，我们立刻能意识到每种数可能出现的位置只构成一个区间 \boldsymbol{[L_x, R_x]}。于是相当于有 m 次查询，每次查询找到最小的一个 x 满足 [L_x, R_x] 与 [l, r] 有交并修改其为它们的交。可以用树状数组套树状数组维护信息，时间复杂度 O(m\log^2 n)。

C：嗯，这听起来是一个有趣的性质了。值得一提的是，虽然 Subtask「每种值出现不超过 5 次」看起来和上面的 Subtask 很接近，但每种数出现的位置并非是 \leq 5 个区间，例如 \{[1, 3], [2, 4], [4, 6]\}，这样的区间集合的 所有解的结构比较复杂，很难直接刻画。

O：然而还有 a_i \leq 5 的部分分......这看起来有点像根号分治题了？我相信我们可以转换一下视角——比如，对于 a_i 的每种可能取值，从大到小依次确定值能取到的每个区间的集合，只需要让这个集合的字典序尽可能小即可。

O：那么现在的问题就是，如何在不重新运行一遍贪心算法的情况下，判定一个集合内加入某个区间后，最小点覆盖数仍然不超过 c 呢？

C：我感觉，我们可以倍增二分出一个前缀，满足这些前缀的点覆盖数恰好等于 c。因为每次被二分出的前缀都会被删掉，所以这一部分的时间复杂度只有 O(m\log^2 m)。现在，我们把原问题变成了 判断是否加入一个新的区间，满足加入它后最小点覆盖数不变。我希望这样的询问有更多性质......

O：你说得对。加入一个新的区间后，最小点覆盖数不变，当且仅当原先存在一种覆盖方案使得某个点在这个区间内......我们还是绕不出这 c 个点的位置的取值范围。虽然这些范围互相约束，但我们可以找出一些更宽泛的限制：如果我们运行原先的贪心算法，从左向右可以依次找出 x_1, \ldots, x_c 的上界 r_1, \ldots, r_c，从右向左可以依次找出 x_c, \ldots, x_1 的下界 l_c, \ldots, l_1。

C：有趣的事情发生了——即使有互相约束的限制，x_i 仍然能够取遍 [l_i, r_i] 内的所有值。只需要让 x_1, \ldots, x_{i-1} 全都取到 r，x_{i+1}, \ldots, x_c 全都取到 l，x_i 取区间内任何一个值，反证法可以说明不产生矛盾。（开始打草稿）而且似乎，在样例里，这些区间总不会相交？

O：你说的对。我们可以直接考虑原算法的流程，说明这一点。由于 l, r 都单调递增，所以不存在完全包含的情况。不失一般性地，假设有区间 [l_i, r_i] 和 [l_j, r_j]，满足 l_i < l_j \leq r_i < r_j。事实上，产生 r_j 这个右边界界当且仅当存在某个区间 [x, r_j] 满足 x > r_i，而这与 l_j \leq r_i 是矛盾的！

C：所以如果加入了一个新的区间，我们可以简单地将其分类为这四种情况：与所有 [l_i, r_i] 区间不相交；完全包含至少某个 [l_i, r_i]；与只有一个 [l_i, r_i] 相交；与 [l_i, r_i] 交于某个后缀，与 [l_{i+1}, r_{i+1}] 交于某个前缀：

O：所以，我们不妨直接把第四类区间的影响记录下来：若 r_i \leq p - 1，则 r_{i+1} \gets \min(r_{i+1}, q)；若 l_{i+1} \geq q - 1，则 l_i \gets \max(l_i, p)。对于每一个区间的 l 和 r 做的对应修改，我们分别维护一个堆，第三类区间修改时，我们暴力取出堆里需要被弹出的元素并递归修改 i \pm 1 即可，这样维护不会让任意时刻 l_i > r_i，这是因为如果如此，必然这个 [p, q] 已经被触发，不可能被再次触发了。而且，容易发现这样做的均摊时间复杂度是正确的。

C：只剩下唯一的一个问题了：如果我们暴力遍历剩余的所有区间，可能会出现大量的第一类区间，导致时间复杂度退化为 O(nm)。

O：这也是不难解决的。均摊分析告诉我们，整个过程只产生了 O(c + r) 个不同的 [l_i, r_i]，其中 r 表示答案为对应 a_i 的区间个数。我们可以对每个新的 [l_i, r_i] 被更新时，求出「和 [l_i, r_i] 区间有交且权值暂未被确定的区间 [L, R] 的最小下标」。

C：这题我会！只需要分讨 l_i \leq L \leq r_i 或 l_i \leq R \leq r_i 以及 L \leq l_i \leq r_i \leq R 两种情况即可，可以用线段树维护，整体的时间复杂度便只有 O((c + r)\log n)，总复杂度 O((n+m)\log n)。

O：这道很困难的题目真的就这样被我们做出来了！回顾一下我们的思考过程，感觉唯一的瓶颈在于刻画插入新的区间后，答案不变的 充要条件；并且需要意识到，这个条件 有很方便的维护手段，其它的部分都很平凡。但是，事到如今，C 君，你不会想要更进一步吗？

C：......此话怎解？

O：我们在倍增二分部分的时间复杂度达到了 O(m\log^2 m)，但后面的数据结构维护却只有一个 \log n。你能把前半部分的做法优化掉一只 \log，使得两部分的时间复杂度平衡吗？

C：让我想想......原来的瓶颈在确定了新加入的区间个数在 [2^{k-1}, 2^k) 并二分的时候，每次二分都需要调用一次排序。但事实上我们可以直接先对这 2^k 个区间排序，然后按顺序提取出所有需要用到的区间即可。于是我们就做到了整体 O(m\log m + (n + m)\log n)。