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