前言

赛时没打出来, 赛后没调出来, 感觉还是挺好的一道题, 记一下

思路

容易发现的是对于 \(a_i \in \{-1, 1\}\) 这样的情况, 我们是可以取到极值中间的所有值的, 因为你从极值的子段中, 取出前缀一定可覆盖到其他值

直观的理解就是每次对子段和的影响最多 \(\pm 1\) , 因此在取的过程中一定可以遍历到

所以我们把序列分成形如 \(A + x + B\) 的部分, 其中 \(A, B\) 的贡献可以用最大 / 最小子序列来求出, \(A + x, x + B\) 的部分可以直接求出

最大的问题是, 全序列合并上 \(x\) 如何做

首先你观察一下他是否仍然具有好的性质, 发现 \(x\) 其实破坏了一些性质, 但不多, 容易观察到的是, 对于包含了 \(x\) 的子段, 这个性质仍然成立

实现

框架

首先处理两个段
然后处理以 \(x\) 作为开头 / 结尾 的 前缀 / 后缀, 放入答案
最后处理合在一起的段

这里合在一起的段需要求包含某个数的最大子段和, 这个怎么做?
容易发现求出以 \(x\) 前一位作为结尾的前缀最大 / 最小, 以 \(x\) 后一位作为开头的后缀最大 / 最小即可

总结

需要具有好的分讨能力, 不逃避对 \(\rm{corner}\) 的思考

对于涉及到 \(1, -1\) 的问题, 善于通过 \(\Delta\) 和前缀后缀来解决

善于手动模拟样例