| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3857 |
| 2 | jiangly | 3747 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3591 |
| 6 | gamegame | 3477 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3463 |
| 9 | ecnerwala | 3451 |
| 10 | heuristica | 3431 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | -is-this-fft- | 161 |
| 3 | Qingyu | 160 |
| 4 | Dominater069 | 158 |
| 5 | atcoder_official | 157 |
| 6 | adamant | 155 |
| 7 | Um_nik | 152 |
| 8 | djm03178 | 151 |
| 9 | luogu_official | 149 |
| 10 | awoo | 148 |
Hey, I want to solve this problem: Given array a of length n handle these queries online (each query in O(logn))
-> l r k (input) which means output the sum of k largest numbers on segment [l,r] in array a.
($$$n <= 10^6$$$ , $$$q <= 10^6$$$ (q is number of queries), the array has only positive integers ($$$a_i <= 10^9$$$))
I know it is possible to do using Wavelet tree.
You can do it using presistent segment tree.
I don't see how it's possible to solve it faster than $$$O(\log^2 n)$$$ with wavelet tree. Are you sure it's doable?