?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
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/