| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
How to solve this problem? I tried a lot of ideas. I used here: 1. Segment tree in every node of segment tree (Gives MLE) 2. Segment Tree in every node of BIT (gives MLE) 3. Avl tree in every node of segment tree (gives TLE) 4. Splay tree in every node of segment tree (gives TLE)
Please, help needed. :( I want to solve this prpblem
Help needed please :'(
Use sqrt-decomposition
sqrt decompose also gets TLE. Already implemented :'(
Use persistent segment tree--first see MKTHNUM on SPOJ. It's a fairly popular problem so there are numerous solutions online. MKTHNUM doesn't have update value queries, but this is also easily implemented with persistent segtrees--just decrement the frequency of the old number, and then increment the frequency of the new number. Both types of queries are log n time.
But in persistent seg-tree, the values of later trees depend on previous. For example: Suppose the trees are at index 1,2,3,4,5,6 Now if i change the frequency of index 3, then the value for 4,5,6 should also be changed, how to handle this? i have no idea about handling this factor. Can you please explain a little bit?
This problem comes from 2015 Multi-University Training Contest 10. And you can find the solution here.
Thanks a lot :) :) I got AC, using BST (Both AVL & Treap) in every node of BIT after seeing your link. Thanks for your help.