题解 P5294 【[HNOI2019]序列】

· · 题解

参考资料

Sol

部分分：m=0

考虑一个更加一般的形式：已知 w_i, A_i \ge 0，要求确定 B_i，使得 B_i \le B_{i+1} 且 \sum w_i(A_i - B_i)^2 最小。

定义一个点集 U 的均值为：让 \sum_{j\in U} w_j (A_j - k)^2 取到最小值的 k。对于这道题，k = \frac{\sum_{j\in U} w_jA_j}{\sum_{j\in U} w_j}（通过求导可得）

引理 1

能达到最优解的 \{ B_i \} 是唯一的。

证明：将 (A_1,A_2,\cdots A_n) 和 (B_1, B_2, \cdots B_n) 看作两个 n 维向量，权值函数可以看作两个点之间的距离。由于不等式组 B_i \le B_{i+1} 的解空间是一个凸集，所以到 A 的距离最短的 B 是唯一的。

引理 2

如果 A_i > A_{i+1}，那么最优解中一定有 B_i = B_{i+1}。

证明：参考 IOI2018 集训队论文《浅谈保序回归问题》

引理 2 启发我们可以考虑这样的一个过程：每一次找到一个满足 A_i > A_{i+1} 的 i，然后将 i 和 i+1 合并。具体地，应该把 (w_i, A_i), (w_{i+1},A_{i+1}) 替换为 (w_i + w_{i+1}, \frac{w_iA_i + w_{i+1}A_{i+1}}{w_i + w_{i+1}})，这样前后的权函数只相差一个常数，直接在合并的时候把这个常数加入答案即可。合并到无法合并的时候，直接令每个 B_i 都取 A_i，这就是最优方案。最终的答案就是在合并的过程中产生的那些常数的和。

由引理 1 可知，无论以任何顺序合并，最终得到的 \{ B_i \} 都是相同的，所以合并过程完成以后得到的那些同值的段（下文称为等值段）也一定是相同的。

正解

把询问离线下来依次处理。对于询问 (x,y)，先处理好只考虑 [1,x-1] 和 [x+1,n] 时，等值段的划分情况（可以用从左到右和从右到左的单调栈分别维护）。

最终的划分方案一定是：保留 [1,x-1] 的等值段划分的一个前缀，保留 [x+1,n] 的等值段划分的一个后缀，剩下的部分和 x 合并为一段。设这个前缀包含了 [1,x-1] 的前 L_0 个等值段，这个后缀包含了 [x+1,n] 的后 R_0 个等值段。设 L_0,R_0 之间（不含 L_0,R_0）的元素合并起来后的权值（也就是它们的平均值）为 v(L_0,R_0)。设 [1,x-1] 中从左到右第 x 段的 A_i 为 lv(x)，设 [x+1,n] 中从右到左第 x 段的 A_i 为 rv(x)。

考虑如何求出 L_0,R_0。我们对 L_0,R_0 的要求是：

考虑这样一个算法：从大到小枚举 R_0，然后求出最大的 L_0，使得 lv(L_0) < v(L_0, R_0)；如果 v(L_0, R_0) < v(R_0) 就退出，把此时的 L_0, R_0 作为答案，否则继续枚举 R_0。

假设 r 为算法结束时的 R_0：任意一个大于 r 的 R_0 显然不可能成为最终的等值段的右端点（因为还可以和右边的段合并）；而任意一个小于 r 的 R_0，v(L_0,R_0) 一定合并了不能合并的段。

所以，算法结束时求出来的 L_0,R_0 就是我们想求的答案。

算法的优化：

总时间复杂度为 O(n \log^2 n)。

Code

my submission on loj.ac