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改过来的。倒着改回去就行。

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

代码

Submission #111853570 - Codeforces
Codeforces. Programming competitions and contests, programming community