Search code examples
c++stlgnu

Order statistics tree using __gnu_pbds for multiset

I am trying to implement an order statistics tree with using __gnu__pbds. I followed this code TREE_ORDER_STATISTICS

But, I need this on a multiset. I was suggested to use a pair to implement this feature CODEFORCES COMMENT

//Main idea is to keep pairs like {elem, id}.

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";

But, how would I use find_by_order(k) for this case?

Solution

  • 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;