自动搬运

查看原文

来自洛谷，原作者为

	tybbs 春江潮水连海平，海上明月共潮生。

搬运于2025-08-24 23:11:51，当前版本为作者最后更新于2025-04-08 14:16:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

参考了 链接 中 $\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)$。