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/
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3843 |
2 | jiangly | 3705 |
3 | Benq | 3628 |
4 | orzdevinwang | 3571 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3530 |
8 | ecnerwala | 3499 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | adamant | 164 |
3 | awoo | 163 |
4 | TheScrasse | 156 |
5 | nor | 153 |
6 | maroonrk | 152 |
6 | -is-this-fft- | 152 |
8 | Petr | 145 |
9 | orz | 144 |
9 | pajenegod | 144 |
Название |
---|
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