AGC044E Random Pawn

首先最大值处一定是直接停下来的，所以可以断环成链，$a_1, a_{n + 1}$ 处为最大值。

设 $f(i)$ 表示当前在 $i$ 的答案，$f(1) = f(n + 1) = a_1$。

$$f(i) = \max(a_i, \frac{f(i - 1) + f(i + 1)}{2} - b_i)$$

接下来的都是没见过的套路：首先先把 $-b_i$ 搞掉，解决办法是两边同时减去一个修正值 $c_i$。

令 $F(i) = f(i) - c_i$，$v_i = a_i - c_i$。

$$F(i) = \max(v_i, \frac{F(i - 1)+ F(i + 1)}{2} - b_i - c_i + \frac{c_{i - 1} + c_{i + 1}}{2})$$

要使得 $-b_i - c_i + \dfrac{c_{i - 1} + c_{i + 1}}{2} = 0$，即 $b_i + c_i = \dfrac{c_{i - 1} + c_{i + 1}}{2}$。

注意这里默认 $F(0) = F(n+ 2) = -\infin$，让式子在 $1, n + 1$ 处成立，令 $c_1 = 0$ 就可以递推了。

$$F(i) = \max(v_i, \frac{F(i - 1)+ F(i + 1)}{2})$$

考虑钦定一些点为固定点，它们都直接取 $v_i$，观察相邻两个固定点 $l, r$。

对于 $l < i < r$，$F(i) = \dfrac{F(i - 1) + F(i + 1)}{2}$，设 $F(l) = v_i = A, F(l + 1) = x$，之间的序列可以表示成：

$$a\ x\ 2x - a\ 3x - 2a\ 4x - 3a\cdots F(r)$$

这是一个等差数列，在二维平面上画出来发现 $\sum_{l\le i\color{red}{<r}} F(i)$ 恰好是 $(l, F(l)), (r, F(r))$ 连起来和 $x$ 轴构成的梯形的面积。

即 $(F(l)+ F(r))\times (r - l) / 2$。

固定点的选择即上凸包。