我正在尝试使用 __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)
?
您需要将比较函数从
less
更改为 less_equal
asn,如下:
typedef tree<
int,
null_type,
less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
使用 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";
用这个代替 s.erase(s.find_by_order(v[a]));