Editorial for Another Contest 1 Problem 1 - Binary String Operations
Submitting an official solution before solving the problem yourself is a bannable offence.
The intended solution for this problem is to maintain an augmented balanced binary search tree (BBST) on the string. We will not be covering full implementation details for the BBST, but will cover how to perform the update and query operations.
We'll start with the query. Each node needs to maintain the maximal length prefix of only 1's, maximal length suffix of only 1's, and maximal length substring of only 1's. For a leaf node, these values are all identically either 0 or 1 depending on the character. When we're merging the result for a non-leaf node, the maximal prefix and suffix can be computed directly by casework. The maximum length substring of only 1's is then either entirely contained within the children, or it must span the non-leaf node, in which case it uses the maximal suffix of the left child and the maximal prefix of the right child.
For the update, imagine that we have a BBST that corresponds to exactly the given string. We flip a lazy
reverse flag on the node. If we ever need to propagate the reverse later on, we swap the left and right children of the root node and flip the
reverse flags on the children. We also need to flip the prefix and suffix lengths for the node.