题解：P12569 [UOI 2023] An Array and Partial Sums

操作两次前缀和，容易证明每次操作一个前缀一定不劣，因此每次操作找到第一个不合法的位置，操作整个前缀。看看是不是只需要两次即可。

操作两次后缀和，同上。

操作一次取反之后变成了操作一次，判一下就行。

操作一次前缀和，后操作一次后缀和。枚举区间 $[l,r]$，我们将 $s$ 的前缀和序列称作 $s'$。那么相当于在 $\min_{i=r+1}^n(s_n-s_r)\geq 0$ 且 $\min_{i=l}^r(s_n-s_r+s'_r-s'_{i-1}-s_{l-1}\times (r-i+1))\geq 0$ 且 $\min_{i=1}^{l-1}(s_n-s_r+s'_r-s'_{l-1}-s_{l-1}\times (r-l+1)+s_{l-1}-s_{i-1})\geq 0$。做到 $O(n^2)$ 是容易的。

考虑分治，那么可以将中间那个限制拆解到 $mid$ 左右两部分，首先枚举 $r$，然后求出最小的 $s_{l-1}$ 使得 $[mid+1,r]$ 上的点全都合法。这个相当于把 $(r-i+1,s_n-s_r+s'_r-s'_{i-1})$ 这些点全都拿出来然后用 $(0,0)$ 取作这个凸包上的切线，然后查询切线的斜率即可。所以只需要动态维护出 $(-i,-s'_{i-1})$ 的凸壳即可。

接下来枚举 $l$，考虑对于一个左端点 $l$，$r$ 需要满足的条件是让 $[l,mid]$ 的点全部合法，首先，查询 $-s'_{i-1}+s_{l-1}\times i$ 的最小值即可求出限制最紧的那个 $i$，这个也可以维护点集凸壳做到。接着，每个 $r$ 都是一条 $s_n-s_r+s'_r-s_{l-1}\times r$ 的关于 $-s_{l-1}$ 的直线，我们不妨求出凸壳之后直接取对于每个 $-s_{l-1}$ 的最大值，然后判断是否满足最紧的限制，如果满足则找到一组合法解直接输出。当然还要判一下 $[1,l-1]$ 与 $[r+1,n]$ 的限制，不过这部分是简单的。

复杂度瓶颈在于上述求切线部分需要一个二分，时间复杂度 $O(n\log^2 n)$。