Codeforces Educational Round 168 Discussion stream (with hints)

When you insert a new character, cost of only 2 elements changes.

Type of cells that can split into 3 components has a fixed pattern.

You can always ensure that any prefix of odd length does not contains more than one extra opening bracket.

Binary search FTW

First read all the queries. Group all queries with same $X$ together and try to answer them in one go.

For a fixed value of $K$, you can binary search to find the $j \cdot k^{\text{th}}$ monster, the fight after which level will change.

Use Merge sort tree along with binary search for $O((N+Q) \cdot \log^4 N)$ solution.

Walk on a Segment Tree to remove one $\log N$ factor.