Hello every one... I need a data structure handling two type of queries. 1. Maximize(l,r,x) 2. Sum(l,r)
I have a O(sqrt(n)*log(n)) solution using sqrt decomposition + set.But I am looking for a better solution. Thanks in advance
Hello every one... I need a data structure handling two type of queries. 1. Maximize(l,r,x) 2. Sum(l,r)
I have a O(sqrt(n)*log(n)) solution using sqrt decomposition + set.But I am looking for a better solution. Thanks in advance
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 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 |
Auto comment: topic has been updated by Shayan.P (previous revision, new revision, compare).
Maximise (l,r,x) means set a[i] = max(a[i], x) ?
Segment tree beats.
It was awesome. Thank you!
Btw do you have any link to Chinese trick like this?
It's possible sqrt decomposition in this case without logarithmic factor? (Lazy sqrt decomposition or dsu approach? Yeah... segment tree beats is cool)
By setting a proper bucket size, you can achieve
per query.
Yeah, I know...,but with potential function analyze (7'-'). u.u maybe, I hope :v