[SegmentTree][SPOJ] BRCKTS

BRCKTS

Question statement:

We will call a bracket word any word constructed out of two sorts of characters: the opening bracket "(" and the closing bracket ")". Among these words we will distinguish correct bracket expressions. These are such bracket words in which the brackets can be matched into pairs such that

• every pair consists of an opening bracket and a closing bracket appearing further in the bracket word
• for every pair the part of the word between the brackets of this pair has equal number of opening and closing brackets

On a bracket word one can do the following operations:

• replacement -- changes the i-th bracket into the opposite one
• check -- if the word is a correct bracket expression

Task

Write a program which

• reads (from standard input) the bracket word and the sequence of operations performed,
• for every check operation determines if the current bracket word is a correct bracket expression,
• writes out the outcome (to standard output). 

My approach:

Well well well. This one took a lot of time for me to understand how exactly I would get the answer for the current node. Initially I thought in the direction of having a single value for each node, which is a total for the range, in which a '(' is counted as a 1 and ')' as a -1.

Then I thought of having valid and invalid nodes, depending on the values of their children. But no point into going into the wrong approach.

Well what struck me was the point that all we needed to see the brackets which were imbalanced. That is, the ones that are not matched. So, I could keep the track of left unmatched brackets and right unmatched brackets, for a node, for the range to which it corresponds. Cool.

How to maintain this property?

That is, given that we have these values for the left and right children of a node, can we get the values for the parent node?

Let's say that the left child has $L_{l}$ left unmatched brackets, and $L_{R}$ right unmatched brackets. Similarly, the right child has $R_{l}$ left unmatched brackets, and $R_{r}$ right unmatched brackets.

Now when we're merging the ranges of the left and the right children, we can see that the left unmatched brackets of the left child and the right unmatched brackets of the right child cancel out!

Example: L: )((()) has one left and one right unmatched bracket
                R: )(      has one left and one right unmatched bracket
So, while merging, we can do $cancelledBrackets = min(L_{l},R_{r})$, and for the parent node:
$$P_{l} = L_{l}- cancelledBrackets+R_{l}$$
And:
$$P_{r} = L_{r}+R_{r}-cancelledBrackets$$

So, this is how we can build our segment tree.

For updation, we can simply change the 1 to 0 and a 0 to 1, for both the left and right brackets, at the leaf. And then we can update the parents using the method as described above.

Here is my elegant code minions: