使用 __gnu_pbds 为多重集排序统计树

Question

我正在尝试使用 __gnu__pbds 实现订单统计树。我遵循了这段代码 TREE_ORDER_STATISTICS

但是，我需要在多集上使用它。有人建议我使用一对来实现此功能 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";

但是，对于这种情况，我将如何使用 find_by_order(k)？

Answer 1

您需要将下面的比较函数从less更改为less_equal asn:

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

Answer 2

使用 less_equal 而不是 less 的缺点是 lower_bound 的工作方式与 upper_bound

一种方法是存储对

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

来源：坚定不移 https://codeforces.com/blog/entry/11080

使用 __gnu_pbds 为多重集排序统计树

Order statistics tree using __gnu_pbds for multiset

c++

stl

gnu