题解：P11983 [JOIST 2025] 展览会 3 / Exhibition 3（暂无数据）

Petit_Souris · 2025-04-28 22:14:20 · 题解

难度已经远比我能独立做出的题高了。不过回顾一下，几个 trick 的叠加也并非无迹可寻。好题，值得学习。

Hint 1：你能编出一个多项式复杂度做法吗？

看到字典序想到逐位贪心。我们考虑从大到小枚举 v，把 v 放在尽可能靠前的位置。

对于每个 v，我们按顺序尝试加入所有还没被覆盖的区间。如果加入之后，覆盖这些区间需要的点数 C\le cnt_v 就是合法的。

判断最小覆盖是一个经典贪心问题，每次选择右端点最小的区间，在其右端点处放一个点即可。

Hint 2：每次选出的区间形态如何？

显然是一段前缀，加上一些零散的区间。这看起来是一句废话，但是我们考虑那一段前缀后面一个位置，他不能选说明加入他之后 C>cnt_v 了，而由于 C 的变化是连续的，这说明这个前缀加入之后 C=cnt_v。

这样后面的区间就必须满足加入之后，不会增加最小覆盖点数。

Hint 3：如何找到这个前缀？直接二分为什么不可行？

二分意味着我们花了至少序列总长的代价去删除一些元素。因此如果每次只删一个复杂度就起飞了。

但是我们可以考虑先倍增。找到最大的 2^k 满足删除前 2^k 个合法，接下来再在 [2^k,2^{k+1}) 内二分，每次暴力跑上面的贪心检验。这样我们就用 \mathcal O(c\log ^2 c) 的代价删除了 c 个元素。总共只删除 m 个元素，因此均摊复杂度正确。

Hint 4：如何判断加入一个区间之后是否需要多一个点覆盖他？

这个结论应该是经典的，可惜我还没见过这样做的题目。有同学知道类似的题目可以在评论区告知我。/kt

我们考虑正反做两遍贪心，求出每个点所在的范围 [tl_j,tr_j]。如果 [L_i,R_i] 和某一个 [tl_j,tr_j] 有交，那么可以调整 j 使得不增加新点。反之，需要增加一个点。

Hint 5：一个区间加入之后，tl,tr 会发生怎样的变化？

以 tr 为例。我们找到 R_i 右边第一个 tr_j，然后一路向右，如果左端点在前面的，对应的最小右端点不到 tr_j 就会一路修改下去。

这样做的修改次数实际上是 \mathcal O(c) 次，因为 tr 相当于保留一些区间的右端点，而一个右端点存活的时间是一段区间。

Hint 6：利用上面的性质编出正解。

找到前缀后，我们只需要快速找出编号最小的，可以加入的区间。

一个简单的想法是用一个小根堆维护所有的编号。这样我们每次对于一个 tr_j，去加入所有和他有交的区间，并贪心跑。

但是这样有一个严重的问题就是，一个区间可能会被放进去很多遍，就退化成 \mathcal O(nm) 了。解决方案也很简单：把所有包含某个 [tl_j,tr_j] 的 [L_i,R_i] 都提前拿出来，这样剩下的区间至多放进去两遍。

找有交的最小编号可以分讨二维偏序关系，用两个线段树维护。

最后整理一下这部分的过程：

• 先得到 tl,tr，对于每个 [tl_j,tr_j]，先把所有包含他的，还未使用过的区间拎出来标记上。
• 接下来，对于每个 [tl_j,tr_j]，找到与其有交的最小编号，加入小根堆。
• 每次取出最小的编号，加入答案。并且重新松弛对应的 j，找到新的最小值。

最终时间复杂度为 \mathcal O(n\log^2 n)，可以通过预处理排序做到 \mathcal O(n\log n)。

实现上细节比较多，一定要理清楚再开始写，写完一部分 debug 掉对应的问题。参考代码。