CF1901F Landscaping

你被委派执行一项非常重要的任务：你负责将一条特定的道路铺平。 这条道路可以表示为一条折线，起点为 $(0, 0)$，终点为 $(n - 1, 0)$，并包含 $n$ 个顶点（包括起点和终点）。第 $i$ 个顶点的坐标为 $(i, a_i)$。 “铺平”道路等价于选择一条从 $(0, y_0)$ 到 $(n - 1, y_1)$ 的线段，使得折线上的所有点都在所选线段之下（或与线段同高）。$y_0$ 和 $y_1$ 可以是实数。 你可以想象这条路有一些坑洼，你开始往上面倒铺路材料，直到道路变平。第 $0$ 个点和第 $n-1$ 个点有无限高的墙，因此铺路材料不会从区间 $[0, n-1]$ 溢出。 铺平道路的代价等于所选线段与折线之间的面积。你希望最小化代价，因此铺平后的道路不一定是水平的。 但有一个问题：你的数据可能已经过时了，所以你派人去测量新的高度。这个人从 $0$ 走到 $n-1$，并把每个顶点 $i$ 的新高度 $b_i$ 发送给你。 由于测量新高度可能需要一段时间，而且你不知道什么时候会被问到，所以每当你收到新的高度 $b_i$ 时，请计算铺平道路的最小代价（以及对应的 $y_0$ 和 $y_1$）。

第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$），表示折线的顶点数。 第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$（$0 \le a_i \le 10^9$；$a_0 = a_{n-1} = 0$），表示各顶点的高度。 第三行包含 $n$ 个整数 $b_0, b_1, \dots, b_{n-1}$（$0 \le b_i \le 10^9$；$b_0 = b_{n-1} = 0$），表示各顶点的新高度。

输出 $n$ 个数：第 $i$ 个数（从 $0$ 开始编号）表示当你已知实际高度 $b_0, \dots, b_i$ 时，“最佳线段”的 $y_0 + y_1$（即使代价最小的线段的两个端点纵坐标之和）。 如果存在多个“最佳线段”，输出其中 $y_0 + y_1$ 最小的。 如果你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。 形式化地，设你的答案为 $x$，标准答案为 $y$。当且仅当 $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-9}$ 时，你的答案被接受。

第一个样例的第一个答案如上图所示。 你可以用如下“最佳线段”得到第二个答案： 你可以用如下“最佳线段”得到第三个答案： 你可以用如下“最佳线段”得到第四个答案： 由 ChatGPT 4.1 翻译