_inaccurate's blog

How to get the position of an element in a set after lower_bound?
By _inaccurate, history, 7 months ago, In English

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?..

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Ordered set

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it 
#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
}
→ Reply
»
7 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Souce 1 — Ordered set
Source 2 — Blog

→ Reply