p3470 sol（POI2008 BBB）

注意到最优解一定是先执行若干次操作 2 再执行操作 1，可以通过调整法证明。

考虑没有操作 2 时的情况。我们需要满足两个条件：

根据条件 2，我们可以轻松算出最终情况有多少 $1/-1$。

根据条件 1，定义 $mn=\min(s_i)$，考虑到修改靠前的 $-1$ 至 $1$ 更优，我们又不得不至少将前 $\lceil\frac{\max(0,-p-mn)}{2}\rceil$ 个减号修改为加号。

所以总修改数就是条件 1 的修改数加上处理完条件 1 后条件 2 的修改数。需要注意的是，处理完条件 1 后我们知道了当时的 $1/-1$ 数，需要与条件 2 算出来的期望值做差。

对于 $1$ 改为 $-1$ 的情况，一定是修改靠后的位置；对于 $-1$ 改为 $1$ 的情况，一定是修改靠前的位置。

有了操作 2，只需要动态维护 $mn$ 即可。