krishan's blog

By krishan, 9 years ago, In English

I know we can solve it using segment tree but i am not unable to proceed. There are two things we need to solve this question are that the sum should be zero (if we consider '(' as 1 and ')' as -1) and i am not able to figure out the other thing? Can you please tell the second point which is important and explain it as well?

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Replace '(' with 1 and ')' with -1 and find the partial sums. The tree will be build on the array with the partial sums.

For each interval store the Minimim and the Maximum element. If you need to update an interval:

min2=min;
max2=max;
max=-min2;
min=-max2

If you need to find out if the sequence is correct, then if the minimum number is 0 and the last number is 0 the answer is YES. Otherwise, the answer is NO.

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

if you replace ( with 1 and ) with  - 1 and take the partial sum(i.e. Si is the sum of all elements from 1 to i) then if Sn is zero and all values of Si are non-negative then the string is correct bracket expression, so all you need is to efficiently support updating the values of Si you can do it with segment tree.