Codeforces Round #698 Nezzar and Binary String 线段树

题意

给你两个由‘0’或者‘1’构成的字符串s和f。现在每天白天，给你一段区间l,r。如果l,r中同时存在‘0’和‘1’，则失败。然后每天晚上在白天的l到r间可以任意改字符，但改动数量要严格小于n/2。

问：经过m天，有没有可能从s改到f。

题解

显然是线段树。因为每天只能改不超过一半，所以从最终的f开始，每天的状态其实固定的。只需要在下一个状态查询l到r间0的个数，就能知道那天晚上改了什么。

比如下一个状态要00011，那么一定是从00000改过来的。倒着改回去就行。

另外，按说其实正着做讲道理也是可以做的。就是维护区间的上一个改动者，然后在白天查询的时候，需要改什么就找具体的上一个改动者，看看他们还有没有足够的余额来改。但是相当复杂，也不知道能不能行。

代码