How to get the position of an element in a set after lower_bound?

Блог пользователя _inaccurate

Автор _inaccurate, история, 2 года назад, По-английски

Hello codeforces! I'm practicing an exercise. My idea is to get the position of the selected element after a binary search on a set. Can you guys help me?..

_inaccurate
2 года назад
10

Комментарии (10)

Написать комментарий?

waipoli

2 года назад, скрыть # |

Ordered set

→ Ответить

_inaccurate

2 года назад, скрыть # ^ |

what's that. Can you explain more for me. Thank you btw:3

→ Ответить

avighnakc

2 года назад, скрыть # ^ |

Just google it. It's a policy based data structure that allows you to do exactly that. Normal std::sets only store the relative location to their back and front elements, (loosely analagous to a linked list), so it's not possible to get the position.

→ Ответить

meTensar

2 года назад, скрыть # ^ |

Hello! Are you from Ukraine? I think I've seen the name Maksym Shvedchenko several times.

→ Ответить

waipoli

2 года назад, скрыть # ^ |

Yes

→ Ответить

2333_

2 года назад, скрыть # |

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

void solve() {
    using kth_set = __gnu_pbds::tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
    
    kth_set s;
    s.insert(3); // {3}
    s.insert(1); // {1, 3};
    auto it = s.lower_bound(0); // 1
    cout << s.order_of_key(*it) << endl; // find({1, 3}, 1) == 0
    auto it2 = s.lower_bound(2); // 3
    cout << s.order_of_key(*it2) << endl; // find({1, 3}, 3) == 1
}

→ Ответить