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

Lynkcat · 2025-05-23 23:15:33 · 题解

先把只需要操作零次和操作一次判掉，操作一次只需要操作整个序列即可，可以证明一定不劣。

有如下结论：操作次数不超过 3。

这是因为我们发现对一个区间 [l,r] 做前缀和本质上是从 a_l,a_{l+1},...,a_{r} 变成 s_{l}-s_{l-1},s_{l+1}-s_{l-1},...,s_{r}-s_{l-1}。做后缀和本质上是从 a_l,a_{l+1},...,a_{r} 变成 s_{r}-s_{l-1},s_{r}-s_{l},...,s_{r}-s_{r-1}。所以如果我们找到 s 最小的位置 x 与 s 最大的位置 y，若 x\leq y，则能在两次之内完成，否则我们把序列取反，两个位置就会反一反，也能在三次之内完成。

接下来就是只需要判断操作两次是否可行即可，分四类情况讨论：

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

• 操作两次后缀和，同上。

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

• 操作一次前缀和，后操作一次后缀和。枚举区间 [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)。