Order statistics tree using __gnu_pbds for multiset

You need to change the comparison function from less to less_equal asn in the following:

typedef tree<
    int,
    null_type,
    less_equal<int>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;

A drawback of using less_equal instead of less is that lower_bound works as upper_bound

One way to do is to store pair

typedef tree<
pair<int, int>,
null_type,
less<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;

int t = 0;

ordered_set me;
...
me.insert({x, t++});
me.erase(me.lower_bound({x, 0}));
cout << me.order_of_key({x, 0}) << "\n";

source: adamant https://codeforces.com/blog/entry/11080

Tags:

C++

Stl

Gnu