This problem I meet very often: there is a set, in which we can add element, also we can erase any element. The problem is to count the number of elements less then x.
Sure, the problem can be solved with treap or something like that, but can it be solved with std::set or other already released data structures?
Any ideas?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
It can be solved with C++ SGI STL tree. link
STL policy based data structures: order_of_key() is what you're looking for.
you too can use sqrt descomposition — mipt item 4.
Actually, if the problem allows that you can doing this work offline, you can easily solve it by using Binary Indexed Tree and Hashing:)
yes! you too can use online segment tree on air! (update and query in [1, maxElement]). O(q logmaxElement). This can be implemented without pointers!
If Max Element is too big to store in an array:
1- Online: You can use dynamic segment tree or any variation of it.
2- Offline: You can use index compression with regular BIT.
sure. :)