I solved it using segment tree. Can it be solved using BIT, Has anyone done that ?
http://www.spoj.pl/problems/BRCKTS/
http://www.spoj.pl/problems/BRCKTS/
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | SecondThread | 145 |
9 | pajenegod | 145 |
Name |
---|
Can u tel me if I use segment tree to solve this question then on which basis should i build the tree..?
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