amit.codename13's blog

Spoj BRCKTS using BIT
By amit.codename13, 15 years ago, In English
I solved it using segment tree. Can it be solved using BIT, Has anyone done that ?
http://www.spoj.pl/problems/BRCKTS/
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can u tel me if I use segment tree to solve this question then on which basis should i build the tree..?

→ Reply
  • »
    »
    14 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    every node in the tree should have the what is its need of brackets. For example you can maintain a variable called balance for which you have the following:

    balance = 0 — the interval to which the node corresponds is balanced balance = x (x>0) — the interval needs x closing brackets balance = x (x<0) — the interval needs x opening brackets

    You should make the changes in the update function and your query function would simply check if the balance of the root is 0

    Update: this balance thing should be implemented by separating the needs for every node this means that you must keep needOpening and needClosing for every node

    → Reply