given an array arr and for each query given l,r,k to ditermine kth minimum number in the range[l,r]. how to determine kth minimum element in a given range by treap thanx in advance
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3845 |
2 | jiangly | 3707 |
3 | Benq | 3630 |
4 | orzdevinwang | 3573 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3532 |
8 | ecnerwala | 3501 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 163 |
2 | adamant | 163 |
4 | maroonrk | 152 |
5 | nor | 151 |
5 | -is-this-fft- | 151 |
7 | TheScrasse | 147 |
7 | atcoder_official | 147 |
9 | Petr | 145 |
10 | pajenegod | 144 |
given an array arr and for each query given l,r,k to ditermine kth minimum number in the range[l,r]. how to determine kth minimum element in a given range by treap thanx in advance
Название |
---|
I don't know about using treap to solve this problem, but user ffao has an awesome guide on how to solve it using a "reverse mergesort" technique: https://www.quora.com/How-can-you-build-a-data-structure-on-an-array-that-returns-kth-order-statistics-on-subarrays-in-logarithmic-time/answer/Fernando-Fonseca-2
why not use persistent segment tree?