P12569 题解
dAniel_lele
·
·
题解
首先进行简答的构造可以发现，至多需要三次即可将所有数非负/非正：取出前缀和最大的位置 pos，如果前缀和最小的位置在左边就对 [1,pos] 跑后缀和再对 [1,n] 跑前缀和，如果前缀和最小的位置在右边就对 [pos+1,n] 跑前缀和再对 [1,n] 跑后缀和，最后再进行一次全局取反操作。
难点在于判操作两次。首先判掉 $[1,n]$ 前缀和/后缀和后全是负的的情况，不妨设第一次做了前缀和，两次操作区间分别为 $[l_1,r_1]$，$[1,n]$，分类讨论：
* 如果第二次也做前缀和：如果 $1\sim l_1-1$ 中所有东西前缀和非负那么完全可以令 $l_1=1$，否则就算是操作第二次前缀和也不可能使 $1\sim l_1-1$ 中所有数非负。因此第一次必然是 $[1,r_1]$，随便上点线段树啥的判一下就行。
* 如果第二次做后缀和：考虑枚举 $l_1$。注意到由于是做后缀和，$r_1$ 有一个最小值的限制。此时，我们希望选 $rsum_{r_1+1}+\sum_{i=l_1}^{r_1}\sum_{j=l_1}^{i}a_j$ 最大的 $r_1$，其中 $rsum_i$ 表示对 $[i,n]$ 后缀做后缀和后 $[i,n]$ 所有数的和。将后面两个 $\sum$ 用前缀和表示会发现可以李超树维护。求出来之后再判一下是否可以满足前缀需求即可。
总复杂度 $O(n\log n)$。