自动搬运

查看原文

来自洛谷，原作者为

	zhongyuwei **

搬运于2025-08-24 22:09:11，当前版本为作者最后更新于2020-04-20 20:13:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

参考资料

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

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$ 的要求是：

• $lv(L_0) < v(L_0,R_0) < rv(R_0)$
• $L_0,R_0$ 之间的元素确实能合并成一段（即合并过程中不存在把 $A_i < A_{i+1}$ 的两个元素合并了的情况）

考虑这样一个算法：从大到小枚举 $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_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$ 来说，最大的满足 $lv(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$ 的情况下求最大的满足 $lv(L_0) < v(L_0, R_0)$ 的 $L_0$
  • 可以证明，如果 $L_0$ 满足条件，那么 $L_0 - 1$ 也满足条件
    • 由于 $lv(L_0) < v (L_0, R_0)$，又因为 $lv(L_0 - 1) < lv(L_0)$，所以 $lv(L_0 - 1) < v(L_0, R_0)$，那么 $lv(L_0 - 1)$ 一定小于 $lv(L_0), v(L_0,R_0)$ 中的元素的平均值（也就是 $v(L_0 - 1,R_0)$），所以 $L_0 - 1$ 一定也满足条件
  • 所以可以直接二分 $L_0$
• 求最大的 $R_0$，使得满足 $lv(L_0) < v(L_0, R_0)$ 的最大的 $L_0$ 也满足 $v(L_0, R_0) < rv(R_0)$
  • 一个重要的观察是，对于某个固定的 $R_0$，满足 $lv(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) \le v(L, R_0) < rv(R_0) < rv(R_0 - 1)$，$v(L',R_0)$ 和 $rv(R_0)$ 都小于 $rv(R_0 - 1)$，所以 $v(L', R_0 - 1)$ 小于 $rv(R_0 - 1)$
  • 所以可以直接二分 $R_0$

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

Code

my submission on loj.ac