英文:
Order Statistic Tree in C++ with duplicates
问题
有没有办法在C++中支持Order statistic tree的重复元素？我已经找到了一种构建次序统计集合的方法在另一个问题中。但它不支持重复键。
例如，如果我有s = {1, 1, 2, 2, 3, 4}。我希望s.find_by_order(0) == s.find_by_order(1) == 1。看起来，如果我们可以使用每个键的值作为计数，并在节点中存储所有子树中的总计数，我们可以实现这个目标。但我不知道如何使用__gnu_pbds来实现这一点。有没有更简单的修改树以支持这一点？
英文:
Is there a way to support duplicates for the Order statistic tree in C++? I have found a way to construct an order statistic set in another question. But it does not support duplicate keys.
For example, if I have s = {1, 1, 2, 2, 3, 4}. I want s.find_by_order(0) == s.find_by_order(1) == 1. It seems that if we can use the value of each key as the count and store the total counts in all subtrees in the node, we can achieve that goal. But I don't know how to do that with __gnu_pbds. Is there a simpler modification of the tree to support that?
答案1
得分: 3
你可以使用一组成对的元素来实现一个多重集合（multiset）。在每对元素中，第一个元素表示值，而第二个元素表示其唯一插入顺序（或时间戳）。这样，我们可以在保持键表示唯一的情况下逻辑上存储重复值。
下面是一个简单的示例：
#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
}
希望这对你有所帮助。
英文:
You may implement a multiset in terms of a set of pairs. In each pair, the first element represents the value, while the second element denotes its unique insertion order (or a timestamp). This way, we can logically store duplicate values while keeping the key representations unique.
Below is a simple example:
#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
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论