P8978 「DTOI-4」中位数

Alex_Wei · 2023-02-09 17:52:45 · 题解

很不错的题目，思路很自然，结论较难证但好猜，思维含量很高。

首先二分答案转化为 01 序列，目标是将所有数全部变成 1。

基本性质：若可操作 I_1, I_2 且 I_1\subset I_2，则操作 I_2 一定更优。

设最优操作序列为 I_1, I_2, \cdots, I_e。

设 1 的权值为 1，0 的权值为 -1，前缀和序列为 s，每次可将权值为正的一段区间全部变成 1。设操作 I 时其权值为 v(I)。

性质 1：对于 1\leq i < e，v(I_i) = 1。

证明：设 v(I_i) > 1，则 I_i 向左或向右扩展 1 一定不会使得 v(I_i)\leq 0。

\square

性质 1 的推论：

• 设操作 I 时区间内原有 1 的数量为 o(I)，消去 0 的数量为 z(I)，若 I\neq [1, n]，则 o(I) = z(I) + 1，进一步有 |I| = o(I) + z(I) = 2o(I) - 1。

性质 2：若存在方案使得 [1, n] 全为 1，则 e\leq \lceil \log_2 n\rceil。

证明：若初始存在 o(I) \geq 2 且 v(I) > 0，即存在 101 或 11 作为子串，则总存在操作序列，使得 o(I_{i + 1}) \geq |I_i| = 2o(I_i) - 1，易知 o(I_i) \geq 2 ^ {i - 1} + 1，则 e\leq \lceil \log_2 n\rceil。

若初始不存在这样的 I，即无法操作长度大于 1 的区间，则无法对序列产生任何影响，即无解。

\square

性质 3：对于任意 1\leq i < j \leq e，I_i\subseteq I_j 或 I_j \subseteq I_i。

证明：

先证明 相交必然包含：考虑两次相交但不包含的操作 I_i = [a, c]，I_j = [b, d]，其中 a < b \leq c < d，则令 I_j = [a, d] 一定合法，因为此时 [a, b) 均为 1。

接下来只需证明 一定相交。我们使用调整法。

找到最后两个相邻且不交的区间 I_j, I_{j + 1}，则 I_{j + 1}\subset I_{j + 2} \subset \cdots \subset I_e。因为 I_e = [1, n]，所以存在 j + 1\leq p < e 使得 I_p\cup I_j = \varnothing，且 I_{p + 1} \cup I_j = I_j。

若 |I_j| \geq |I_p|，我们可以将 I_{j + 1}\sim I_p 全部取消，替换为 I_j 的 “超区间” I_j\subset I\subseteq I_{p + 1}，这样消去 0 的数量为 |I_j| - 1\geq |I_p| - 1，而 I_{j + 1}\sim I_p 消去的 0 的数量显然不超过 |I_p| - 2，所以替换后 I_{p + 1} 的权值一定增加，而操作数不增。

若 |I_j| < |I_p|，类似地，取消操作 I_j，替换为在 I_p 后插入 I_p 的 “超区间” I_p\subset I\subseteq I_{p + 1}，I_{p + 1} 的权值增加，而操作数不变。

调整后，相邻且不交的区间的位置单调递减，因此调整总可以结束。

\square

有了性质 2 和性质 3，我们可以设计 DP f_{i, l, r} 表示 I_i = [l, r] 是否可行。转移暴力枚举扩展区间，单次检查时间复杂度 \mathcal{O}(n ^ 4\log n)。

根据基本性质，对于每个 l，我们只关心最大的 r 使得 f_{i, l, r} = 1。因此，考虑 值域定义域互换 的套路，设 f_{i, l} 表示从 l 开始，最大的 r 使得原 f_{i, l, r} 等于 1。

再根据基本性质，如果 p < q 且 f_{i, p} \geq f_{i, q}，那么 f_{i, q} 是无用的。因此，从 f_{i - 1} \to f_i 时，我们只关心所有不被包含的 I_l = [l, f_{i - 1, l}] 区间，即左右端点单调递增。

设 c(I) 表示操作 I = [l, r] 后相对于原序列，对包含 I 的区间的权值产生的贡献，即 r - l + 1 - (s_r - s_{l - 1})。考虑检查 f_{i, l} 能否为 p，那么我们求出所有使得 [j, f_{i - 1, j}]\subseteq [l, p] 的 c([j, f_{i - 1, j}]) 的最大值 c_{\max}，那么 s_p - s_{l - 1} 加上 c_{\max} 之后应为正数，即 s_{l - 1} - c_{\max} < s_p。

这样，我们有了单次检查 \mathcal{O}(n ^ 2\log n) 的做法。结合递增性质，换成扫描线 + 单调栈 + 线段树二分即可 \mathcal{O}(n\log ^ 2 n)，但总复杂度 \mathcal{O}(n \log ^ 3 n) 及大常数仍无法通过。

我们进一步利用递增性质，从后往前扫描线。加入区间 I_l 时，权值小于 c(I_l) 的区间就无用了。这启发我们使用单调队列，从队头到队尾 区间位置从右往左，同时 权值递减。我们希望找到队列中的第一个位置 I_p，使得存在 q \geq f_{i - 1, p} 且 s_{l - 1} - c(I_p) < s_q。预处理 g_i 表示使得 s_q \geq i 的最大的 q，则相当于检查是否有 g(s_{l - 1} - c(I_p) + 1)\geq f_{i - 1, p}。