Hello friends I am trying to solve http://www.spoj.com/problems/GSS1/ but I am a little weak in segment trees So I am not able to figure out How my preprocessing function will look like and also If someone could explain a way to solve this without segment trees (as there are only queries no updation required)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Here is my approach with
complexity.
Can't we do it in O(NlogN) by using sparse table algorithm?
Well, i think there is no difference between sparse table and segment tree for this problem, except memory ability. If one figured out how to merge two constructive part he would think about doing it via segment tree with O(N) memory.
But above approach is completely different from those two(segment tree and sparse table).
Thanks for your reply. I had a doubt in the sparse table implementation. Once we have pre-processed the values,in the query function we'll have to use the binary representation of j-i to calculate F[i][j], right? I have worked out a solution.I was wondering if this approach is correct.
This is my code, http://ideone.com/kw0T2S
I am implementing segment tree/sparse table algorithm for the first time,so kindly help me out.
Here