【题解】Luogu-P4756 Added Sequence

P4756 Added Sequence

给定数组 $a_i$，定义 $f(i,j)=|\sum_{p=i}^j a_p|$，称数组的美丽度为 $\max\{f(i,j)\}(i\le j)$。每次给定一个 $x$，$m$ 次询问，每次询问在将整个数组加上 $x$ 的基础上的美丽度。询问相互独立。
$n\le 2\times 10^5$。

$\texttt{Solution}$

令 $s_i = \sum_{p=1}^i a_i$，那么 $f(i,j) = |s_j-s_i|$。

如果 $f(i,j)$ 最大，那一定是最大的 $s$ 减去最小的 $s$。那答案就是：

$$\max_{i=1}^n\{s_i\} - \min_{i=1}^n\{s_i\}$$

对于将整个数组加上 $x$ 的操作，在前缀和数组上，$s_i$ 变为 $s_i + i \times x$，这是个一次函数的形式。不妨设 $g_i(x)$ 是 $s_i$ 所产出的一次函数，那么有：

$$g_i(x) = ix +s_i$$

不难发现，现在我们需要寻找的值一定就在这些一次函数的上凸壳与下凸壳上。则首先维护出上下凸壳，然后每次对于一个 $x$，二分出他所在的位置，即可得到在 $x$ 处取哪一个位置的前缀和最优。

对于两个函数 $g_i(x)$ 与 $g_j(x)$，其交点满足：$ix+s_i=jx+s_j$，那么 $x = \dfrac{s_i-s_j}{j-i}$。如何通过一次函数解析式来维护凸壳呢？考虑到任意斜率不相同，则按照斜率从小到大加入直线，每次只需要考虑新加入的直线与栈顶两条直线的交点的横坐标的大小关系即可。

时间复杂度 $\mathcal{O}(m\log n)$。