LOJ3059 「HNOI2019」序列

参考资料

IOI2018 集训队论文高睿泉《浅谈保序回归问题》
大米饼的博客

Sol

部分分： $m = 0$

考虑一个更加一般的形式：已知 $w_{i}, A_{i} \geq 0$ ，要求确定 $B_{i}$ ，使得 $B_{i} \leq 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_{j} A_{j}}{\sum_{j \in U} w_{j}}$ （通过求导可得）

引理 1

能达到最优解的 ${B_{i}}$ 是唯一的。

证明：将 $(A_{1}, A_{2}, \dots A_{n})$ 和 $(B_{1}, B_{2}, \dots B_{n})$ 看作两个 $n$ 维向量，权值函数可以看作两个点之间的距离。由于不等式组 $B_{i} \leq 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_{i} A_{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}$ 为 $l v (x)$ ，设 $[x + 1, n]$ 中从右到左第 $x$ 段的 $A_{i}$ 为 $r v (x)$ 。

考虑如何求出 $L_{0}, R_{0}$ 。我们对 $L_{0}, R_{0}$ 的要求是：

$l v (L_{0}) < v (L_{0}, R_{0}) < r v (R_{0})$
$L_{0}, R_{0}$ 之间的元素确实能合并成一段（即合并过程中不存在把 $A_{i} < A_{i + 1}$ 的两个元素合并了的情况）

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

对于某个固定的 $R_{0}$ 来说
- 考虑某个比求出的 $L_{0}$ 更小的 $L_{0}^{'}$ ： $v (L_{0}^{'}, R_{0})$ 一定合并了不能合并的段（即满足 $A_{i} < A_{i + 1}$ 的两个段）
- 考虑某个比求出的 $L_{0}$ 更大的 $L_{0}^{'}$ ： $v (L_{0}^{'}, R_{0})$ 一定还能和左边的段合并，所以不可能和 $R_{0}$ 一起作为最终的等值段
故而，对于固定的 $R_{0}$ 来说，最大的满足 $l v (L_{0}) < v (L_{0}, R_{0})$ 的 $L_{0}$ 是唯一可能使 $(L_{0}, R_{0})$ 合法的 $L_{0}$

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

所以，算法结束时求出来的 $L_{0}, R_{0}$ 就是我们想求的答案。

算法的优化：

在已知 $R_{0}$ 的情况下求最大的满足 $l v (L_{0}) < v (L_{0}, R_{0})$ 的 $L_{0}$
- 可以证明，如果 $L_{0}$ 满足条件，那么 $L_{0} - 1$ 也满足条件
  - 由于 $l v (L_{0}) < v (L_{0}, R_{0})$ ，又因为 $l v (L_{0} - 1) < l v (L_{0})$ ，所以 $l v (L_{0} - 1) < v (L_{0}, R_{0})$ ，那么 $l v (L_{0} - 1)$ 一定小于 $l v (L_{0}), v (L_{0}, R_{0})$ 中的元素的平均值（也就是 $v (L_{0} - 1, R_{0})$ ），所以 $L_{0} - 1$ 一定也满足条件
- 所以可以直接二分 $L_{0}$
求最大的 $R_{0}$ ，使得满足 $l v (L_{0}) < v (L_{0}, R_{0})$ 的最大的 $L_{0}$ 也满足 $v (L_{0}, R_{0}) < r v (R_{0})$
- 一个重要的观察是，对于某个固定的 $R_{0}$ ，满足 $l v (L_{0}) < v (L_{0}, R_{0})$ 的最大的 $L_{0}$ ，就是使 $v (L_{0}, R_{0})$ 取到最大值的 $L_{0}$
- 可以证明，如果 $R_{0}$ 满足条件，那么 $R_{0} - 1$ 也满足条件
  - 设 $R_{0}$ 求出的 $L_{0}$ 为 $L$ ， $R_{0} - 1$ 求出的 $L$ 为 $L^{'}$ ，那么 $v (L^{'}, R_{0}) \leq v (L, R_{0}) < r v (R_{0}) < r v (R_{0} - 1)$ ， $v (L^{'}, R_{0})$ 和 $r v (R_{0})$ 都小于 $r v (R_{0} - 1)$ ，所以 $v (L^{'}, R_{0} - 1)$ 小于 $r v (R_{0} - 1)$
- 所以可以直接二分 $R_{0}$

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

Code

my submission on loj.ac

参考资料

Sol

部分分：m=0

引理 1

引理 2

正解

Code

部分分： $m = 0$