Order Statistic Tree in C++ with duplicates

Question

有没有办法支持 C++ 中订单统计树的重复项？我在另一个问题中找到了构建顺序统计集的方法。但它不支持重复键。

例如，如果我有s = {1, 1, 2, 2, 3, 4}. 我想s.find_by_order(0) == s.find_by_order(1) == 1。看来，如果我们能用每个键的值作为计数，并将总计数存储在节点中的所有子树中，我们就可以实现这个目标。但我不知道如何做到这一点__gnu_pbds。是否有对树进行更简单的修改来支持这一点？

Answer 1

您可以根据一组对来实现多重集。在每一对中，第一个元素表示值，而第二个元素表示其唯一的插入顺序（或时间戳）。这样，我们就可以在逻辑上存储重复值，同时保持键表示的唯一性。

下面是一个简单的例子：

#include <iostream> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std; 
using namespace __gnu_pbds; 

struct ost_multiset {
    typedef pair<int, unsigned> pii;
    typedef tree<
        pii,
        null_type,
        less<pii>,
        rb_tree_tag,
        tree_order_statistics_node_update
    > ost;

    ost s;
    unsigned cnt = 0;

    ost_multiset() = default;
    ost_multiset(initializer_list<int> l) {
        for (int x : l) {
            insert(x);
        }
    }
    void insert(int x) {
        s.insert({x, cnt++});
    }
    ost::iterator find_by_order(int k) {
        return s.find_by_order(k);
    }
    // erase all elements with value x
    void erase(int x) {
        auto it = s.lower_bound({x, 0});
        while (it != s.end() && it->first == x) {
            erase(it++);
        }
    }
    // erase a single element
    void erase(ost::iterator it) {
        s.erase(it);
    }

    size_t size() const {
        return s.size();
    }
};

int main() {
    ost_multiset s {1, 1, 2, 2, 3, 4};
    for (int i = 0; i < s.size(); ++i) {
        cout << s.find_by_order(i)->first << ",\n"[i == s.size() - 1];
    }
    // the above loop prints 1, 1, 2, 2, 3, 4
    
    s.erase(1);
    for (int i = 0; i < s.size(); ++i) {
        cout << s.find_by_order(i)->first << ",\n"[i == s.size() - 1];
    }
    // the above loop prints 2, 2, 3, 4

    s.erase(s.find_by_order(0));
    for (int i = 0; i < s.size(); ++i) {
        cout << s.find_by_order(i)->first << ",\n"[i == s.size() - 1];
    }
    // the above loop prints 2, 3, 4
}