?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 172 |
2 | adamant | 164 |
3 | awoo | 163 |
4 | TheScrasse | 160 |
5 | nor | 157 |
6 | maroonrk | 155 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
9 | orz | 145 |
9 | pajenegod | 145 |
Название |
---|
No, you can't. However, if you use ordered set, you can do this in $$$O(log(N))$$$
No, it is not possible to calculate std::distance() for iterators in std::set with O(N) complexity. The reason for this is that std::set is implemented as a balanced binary search tree, which means that the elements are stored in a non-contiguous order. As a result, the distance between two iterators in a std::set can only be calculated by traversing the tree from one iterator to the other, which takes O(log n) time complexity, where n is the number of elements in the set. Therefore, std::distance() for iterators in std::set has a worst-case time complexity of O(log n).
no lol iterator traversal on
std::set
is $$$O(\text{distance})$$$, so basically this is $$$O(N)$$$You can use
__gnu_pbds::tree
and set node update totree_order_statistics_node_update
.After that just call
order_of_key
to find distance between two elements in $$$O(\log N)$$$ time.For
std::set<Key,Compare,Allocator>::iterator
, it is mentioned in https://en.cppreference.com/w/cpp/iterator/distance that its time complexity is linear. Not sure if we could do better asstd::set<>
is too packaged.it is impossible to get distance or indicies in a set in less than O(N) time, however using the ordered set data structure can do this in O(log N) time.
https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/
You can use segment tree is similar to set and O(log(n))