Do you how to think of it, or which method to solve it? With these problems its typically to think of them as prefix sums where '(' = 1 and ')' = -1, we could do the other way around but this is more intuitive to me. If the cumulative "balace" is always non negative in the range and the total balance is 0 in the range it is balanced.

For method you just have to some method to minimize *= -1 and if the amount of brackets not even it is always "Impossible" otherwise it's possible

Hi!

It's just a Segment Tree, in each node of the segment tree you can store two numbers: # of open parenthesis not matched in this range, # of close parenthesis not matched in this range.

When you need to merge two intervals, you only match open parenthesis of the left child with the close parenthesis of the right child as much as you can and the rest just add it to the respective field.

For more details, this is my code: https://pastebin.com/BwJ1bv2C

Hope it can be useful!