专栏文章

P11983 Solution

iirrisshirro
P11983题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mioyo4ao
此快照首次捕获于
2025/12/03 03:18
3 个月前
此快照最后确认于
2025/12/03 03:18
3 个月前
查看原文
O：今天我们来做 P11983 [JOIST 2025] 展览会 吧。派对的时候，大家都说这个题是好题。
有一个序列 a1,…,ana_1, \ldots, a_n，请任意重排之，令 bi=max⁡(ali,…,ari)，b_i = \max(a_{l_i}, \ldots, a_{r_i})，最大化 b1,…,bmb_1, \ldots, b_m 的字典序。1≤ai≤n≤1051 \leq a_i \leq n \leq 10^5，1≤m≤1051 \leq m \leq 10^5。3 秒 / 1 GB。
C：看完这个题之后，我能提出一些简单的想法，比如说 O(n2m)\mathcal O(n^2m)......只需要依次枚举每个区间对应的权值并判断即可，但是，这太暴力了，而且很难再优化了。
O：有一个部分分 ai=ia_i = i 看起来很有意思。如果每种数只出现一次，我们立刻能意识到每种数可能出现的位置只构成一个区间 [Lx,Rx]\boldsymbol{[L_x, R_x]}。于是相当于有 mm 次查询，每次查询找到最小的一个 xx 满足 [Lx,Rx][L_x, R_x] 与 [l,r][l, r] 有交并修改其为它们的交。可以用树状数组套树状数组维护信息，时间复杂度 O(mlog⁡2n)\mathcal O(m\log^2 n)。
C：嗯，这听起来是一个有趣的性质了。值得一提的是，虽然 Subtask「每种值出现不超过 55 次」看起来和上面的 Subtask 很接近，但每种数出现的位置并非是 ≤5\leq 5 个区间，例如 {[1,3],[2,4],[4,6]}\{[1, 3], [2, 4], [4, 6]\}，这样的区间集合的 所有解的结构比较复杂，很难直接刻画。
O：然而还有 ai≤5a_i \leq 5 的部分分......这看起来有点像根号分治题了？我相信我们可以转换一下视角——比如，对于 aia_i 的每种可能取值，从大到小依次确定值能取到的每个区间的集合，只需要让这个集合的字典序尽可能小即可。
O：那么现在的问题就是，如何在不重新运行一遍贪心算法的情况下，判定一个集合内加入某个区间后，最小点覆盖数仍然不超过 cc 呢？
C：我感觉，我们可以倍增二分出一个前缀，满足这些前缀的点覆盖数恰好等于 cc。因为每次被二分出的前缀都会被删掉，所以这一部分的时间复杂度只有 O(mlog⁡2m)\mathcal O(m\log^2 m)。现在，我们把原问题变成了 判断是否加入一个新的区间，满足加入它后最小点覆盖数不变。我希望这样的询问有更多性质......
O：你说得对。加入一个新的区间后，最小点覆盖数不变，当且仅当原先存在一种覆盖方案使得某个点在这个区间内......我们还是绕不出这 cc 个点的位置的取值范围。虽然这些范围互相约束，但我们可以找出一些更宽泛的限制：如果我们运行原先的贪心算法，从左向右可以依次找出 x1,…,xcx_1, \ldots, x_c 的上界 r1,…,rcr_1, \ldots, r_c，从右向左可以依次找出 xc,…,x1x_c, \ldots, x_1 的下界 lc,…,l1l_c, \ldots, l_1。
C：有趣的事情发生了——即使有互相约束的限制，xix_i 仍然能够取遍 [li,ri][l_i, r_i] 内的所有值。只需要让 x1,…,xi−1x_1, \ldots, x_{i-1} 全都取到 rr，xi+1,…,xcx_{i+1}, \ldots, x_c 全都取到 ll，xix_i 取区间内任何一个值，反证法可以说明不产生矛盾。（开始打草稿）而且似乎，在样例里，这些区间总不会相交？
O：你说的对。我们可以直接考虑原算法的流程，说明这一点。由于 l,rl, r 都单调递增，所以不存在完全包含的情况。不失一般性地，假设有区间 [li,ri][l_i, r_i] 和 [lj,rj][l_j, r_j]，满足 li<lj≤ri<rjl_i < l_j \leq r_i < r_j。事实上，产生 rjr_j 这个右边界界当且仅当存在某个区间 [x,rj][x, r_j] 满足 x>rix > r_i，而这与 lj≤ril_j \leq r_i 是矛盾的！
C：所以如果加入了一个新的区间，我们可以简单地将其分类为这四种情况：与所有 [li,ri][l_i, r_i] 区间不相交；完全包含至少某个 [li,ri][l_i, r_i]；与只有一个 [li,ri][l_i, r_i] 相交；与 [li,ri][l_i, r_i] 交于某个后缀，与 [li+1,ri+1][l_{i+1}, r_{i+1}] 交于某个前缀：
  • 我们不希望统计第一类区间；
  • 第二类区间不会对任何 [li,ri][l_i, r_i] 产生影响；
  • 第三类区间只会对某个 [li,ri][l_i, r_i] 的界产生影响。
  • 第四类区间......？乍一看它不会影响任何 [li,ri][l_i, r_i] 的取值，因为我们之前的构造方式仍然成立。但一旦结合后续产生的若干第三类区间，第四类区间的制约条件可能就会发生作用，导致 [li,ri][l_i, r_i] 产生变化。
O：所以，我们不妨直接把第四类区间的影响记录下来：若 ri≤p−1r_i \leq p - 1，则 ri+1←min⁡(ri+1,q)r_{i+1} \gets \min(r_{i+1}, q)；若 li+1≥q−1l_{i+1} \geq q - 1，则 li←max⁡(li,p)l_i \gets \max(l_i, p)。对于每一个区间的 ll 和 rr 做的对应修改，我们分别维护一个堆，第三类区间修改时，我们暴力取出堆里需要被弹出的元素并递归修改 i±1i \pm 1 即可，这样维护不会让任意时刻 li>ril_i > r_i，这是因为如果如此，必然这个 [p,q][p, q] 已经被触发，不可能被再次触发了。而且，容易发现这样做的均摊时间复杂度是正确的。
C：只剩下唯一的一个问题了：如果我们暴力遍历剩余的所有区间，可能会出现大量的第一类区间，导致时间复杂度退化为 O(nm)\mathcal O(nm)。
O：这也是不难解决的。均摊分析告诉我们，整个过程只产生了 O(c+r)\mathcal O(c + r) 个不同的 [li,ri][l_i, r_i]，其中 rr 表示答案为对应 aia_i 的区间个数。我们可以对每个新的 [li,ri][l_i, r_i] 被更新时，求出「和 [li,ri][l_i, r_i] 区间有交且权值暂未被确定的区间 [L,R][L, R] 的最小下标」。
C：这题我会！只需要分讨 li≤L≤ril_i \leq L \leq r_i 或 li≤R≤ril_i \leq R \leq r_i 以及 L≤li≤ri≤RL \leq l_i \leq r_i \leq R 两种情况即可，可以用线段树维护，整体的时间复杂度便只有 O((c+r)log⁡n)\mathcal O((c + r)\log n)，总复杂度 O((n+m)log⁡n)\mathcal O((n+m)\log n)。
O：这道很困难的题目真的就这样被我们做出来了！回顾一下我们的思考过程，感觉唯一的瓶颈在于刻画插入新的区间后，答案不变的 充要条件；并且需要意识到，这个条件 有很方便的维护手段，其它的部分都很平凡。但是，事到如今，C 君，你不会想要更进一步吗？
C：......此话怎解？
O：我们在倍增二分部分的时间复杂度达到了 O(mlog⁡2m)\mathcal O(m\log^2 m)，但后面的数据结构维护却只有一个 log⁡n\log n。你能把前半部分的做法优化掉一只 log⁡\log，使得两部分的时间复杂度平衡吗？
C：让我想想......原来的瓶颈在确定了新加入的区间个数在 [2k−1,2k)[2^{k-1}, 2^k) 并二分的时候，每次二分都需要调用一次排序。但事实上我们可以直接先对这 2k2^k 个区间排序，然后按顺序提取出所有需要用到的区间即可。于是我们就做到了整体 O(mlog⁡m+(n+m)log⁡n)\mathcal O(m\log m + (n + m)\log n)。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...