题解：CF1758F Decent Division

这个题感觉不是很难。

分类讨论操作：

$1$ 变 $0$ 。考虑本来包含 $i$ 这个位置的区间 $[l,r]$ 。令 $1$ 权值为 $1$ ， $0$ 权值为 $-1$ ， $s(l,r)$ 表示 $[l,r]$ 区间权值和。则本来有 $s(l,r)=0$ ，所以 $s(l,i-1)+s(i+1,r)=-1$ 。所以 $s(l,i-1)$ 和 $s(i+1,r)$ 中总有一个是负数。不妨令其为 $s(l,i-1)$ ，则找到第一个位置 $x \leq i - 1$ 满足 $s(l,x)=-1$ ，显然 $S_x=0$ ，将 $[l,x)$ 划分出来。此时 $s(x+1,r)=1$ ，故 $s(x+1,i-1)+s(i+1,r)=0$ 。若两者都为 $0$ 则直接划分，否则一侧有负数同理找到第一个前缀和为 $-1$ 的位置划分，那么剩下这一段本来的和就是 $2$ ，将 $1$ 变为 $0$ 后和正好变为 $0$ ，恰好符合限制。
$0$ 变 $1$ 。若本来这个 $0$ 在某段内，则变为 $1$ 后段的总和从 $0$ 变为了 $2$ 。此时考虑右端点的下一个字符，若是 $0$ 则可将其纳入段内，否则将这段与原段合并。不断往后做即可。另一方面，若本来 $0$ 不在段内，若下一个字符也是 $0$ ，操作后 $10$ 就是合法段，否则类似之前的继续往后合并段即可。

整个过程不难用线段树维护。复杂度

O(n \log n)

。操作次数线性。

文章操作