P12569 题解

首先进行简答的构造可以发现，至多需要三次即可将所有数非负/非正：取出前缀和最大的位置 $pos$，如果前缀和最小的位置在左边就对 $[1,pos]$ 跑后缀和再对 $[1,n]$ 跑前缀和，如果前缀和最小的位置在右边就对 $[pos+1,n]$ 跑前缀和再对 $[1,n]$ 跑后缀和，最后再进行一次全局取反操作。

$0$ 次是好判的。如果只允许操作 $1$ 次可以推导出只有可能是 $[1,n]$ 前缀和/后缀和或全局翻转。

难点在于判操作两次。首先判掉 $[1,n]$ 前缀和/后缀和后全是负的的情况，不妨设第一次做了前缀和，两次操作区间分别为 $[l_1,r_1]$，$[1,n]$，分类讨论：

总复杂度 $O(n\log n)$。