| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | adamant | 157 |
| 6 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | djm03178 | 153 |
I have a array of numbers. The size of the array is about 1e5. This count of operations is about 1e5.
There are 3 types of operation:
change the i-th (position) number;
query the k-th (big or small) number's value;
query the i-th (position) number's rank (big or small).
I have to implement BST myself?
If you want to solve that problem using BST, yes, you have to implement it, java and c++ have implemented BSTs but its not easy to augment the nodes (or impossible?).
Because RB tree is implemented in STL, maybe it's possible to use BST not implemented by myself.
In std::map values can be modified. For modifying keys, one will have to .erase() old one and insert new one.
Well, a segment tree would be enough :).
Could you please give some more details?
Compress all integers to the range 1...2e5.
Then make a segment tree on values (1, 2e5) in which node (i, j) holds the count of integers in the range [i,j] in the entire array
Queries should be pretty similar to the binary search tree version from here.
For query 3, I can solve it in O(log(n)).
But for query 2, I can solve it using binary search. Time O(log2(n)).
If I want query the value(query 2's answer)'s original position, I don't know how to solve it. Please help...
Querying "original position" of k-th number doesn't make sense here as there could be multiple elements with the same value.
But ofcourse, you can access the set of positions occupied by the k-th number by associating a
std::setwith each number.This requires some knowledge of how the segtree is organized.
Think about how you would do it in a bst: you'd look at the count of elements in the left subtree, and decide based on that whether to go to left or right subtree.
Here do the same thing: recurse from the top to bottom, if the count in the left subtree is not enough, go the right, else go to the left, until you reach the element you want.
You can do the same thing with a bit, which would be even faster. I believe the topcoder tutorial has code for that.
You can also use order statistics tree implemented in SGI STL.
Also somebody above recommended to compress numbers with segment tree. But you can solve problem with segment tree without compressing like described here. Also in that entry described how to solve the second query in
.
Thanks!!!
This is what I want really!
Thanks again~ :D