Persistent Ordered Multiset
(ds/bst/persistent_ordered_multiset.hpp)
- View this file on GitHub
- Last update: 2026-08-12 03:11:00+09:00
- Include:
#include "ds/bst/persistent_ordered_multiset.hpp"
Overview
PersistentOrderedMultiset is a path-copying red-black tree for multisets.
Updates, splits, and merges return new versions and leave every input version
available. Equal keys are stored as one leaf with a multiplicity.
Nodes are stored in a specialization-wide stable-slot pool and refer to children by integer index. Intrusive reference counts reclaim a node after its final dependent version or parent is released, and later updates reuse its slot.
The _inplace methods mutate this handle while preserving other versions.
Changing the multiplicity of an existing leaf uses copy-on-write and reuses
unique search-path nodes. Inserting a new distinct key or removing its final
copy still runs the persistent red-black split/merge algorithm because that
operation changes and rebalances the tree topology.
Pointers returned by bound and predecessor/successor methods remain valid only while a live version depends on the pointed-to node.
Template Parameters
-
T: The key type. -
Compare: Ordering predicate. Defaults tostd::less<T>.
Trees passed to merge must use equivalent comparator state.
Constructors
-
PersistentOrderedMultiset()Constructs an empty multiset. ($O(1)$) -
PersistentOrderedMultiset(Compare compare)Constructs an empty multiset with a custom comparator. ($O(1)$) -
PersistentOrderedMultiset(std::initializer_list<T> init)Constructs a multiset from an initializer list. ($O(N \log N)$) -
PersistentOrderedMultiset(Iterator first, Iterator last)Constructs a multiset from a range. ($O(N \log N)$)
Methods
| Method | Description | Complexity |
|---|---|---|
int size() const |
Returns the total number of elements, including duplicates. | $O(1)$ |
int unique_size() const |
Returns the number of distinct keys. | $O(1)$ |
bool empty() const |
Returns whether the multiset is empty. | $O(1)$ |
void release() |
Releases this version immediately and makes this handle empty. | $O(F)$ |
std::size_t node_count() const |
Returns live nodes for this T, Compare specialization. |
$O(1)$ |
PersistentOrderedMultiset clear() const |
Returns an empty multiset with the same comparator. | $O(1)$ |
PersistentOrderedMultiset insert(T key, int multiplicity = 1) const |
Returns a new multiset with multiplicity copies of key inserted. |
$O(\log N)$ |
void insert_inplace(T key, int multiplicity = 1) |
Inserts into this version; multiplicity-only changes use copy-on-write. | $O(\log N)$ |
PersistentOrderedMultiset erase_one(const T& key) const |
Returns a new multiset with one copy of key removed if it exists. |
$O(\log N)$ |
PersistentOrderedMultiset erase(const T& key) const |
Alias for erase_one(key). |
$O(\log N)$ |
bool erase_one_inplace(const T& key), bool erase_inplace(const T& key)
|
Removes one copy in this version and returns whether it existed. Multiplicity-only changes use copy-on-write. | $O(\log N)$ |
PersistentOrderedMultiset erase_all(const T& key) const |
Returns a new multiset with all copies of key removed if it exists. |
$O(\log N)$ |
bool erase_all_inplace(const T& key) |
Removes all copies in this version and returns whether the key existed. | $O(\log N)$ |
bool contains(const T& key) const |
Returns whether key exists. |
$O(\log N)$ |
int count(const T& key) const |
Returns the multiplicity of key. |
$O(\log N)$ |
const T* find_by_order(int k) const |
Returns a pointer to the 0-indexed k-th smallest element. Requires 0 <= k < size(). |
$O(\log N)$ |
T kth(int k) const |
Returns the 0-indexed k-th smallest element by value. Requires 0 <= k < size(). |
$O(\log N)$ |
int order_of_key(const T& key) const |
Returns the number of elements strictly less than key. |
$O(\log N)$ |
int count_less(const T& key) const |
Alias for order_of_key(key). |
$O(\log N)$ |
int count_less_equal(const T& key) const |
Returns the number of elements less than or equal to key. |
$O(\log N)$ |
int count_greater(const T& key) const |
Returns the number of elements strictly greater than key. |
$O(\log N)$ |
int count_greater_equal(const T& key) const |
Returns the number of elements greater than or equal to key. |
$O(\log N)$ |
const T* lower_bound(const T& key) const, const T* min_ge(const T& key) const
|
Returns the smallest element greater than or equal to key, or nullptr. |
$O(\log N)$ |
const T* upper_bound(const T& key) const, const T* min_gt(const T& key) const
|
Returns the smallest element strictly greater than key, or nullptr. |
$O(\log N)$ |
const T* max_le(const T& key) const |
Returns the largest element less than or equal to key, or nullptr. |
$O(\log N)$ |
const T* max_lt(const T& key) const |
Returns the largest element strictly less than key, or nullptr. |
$O(\log N)$ |
const T* min() const, const T* max() const
|
Returns the minimum or maximum element, or nullptr if the multiset is empty. |
$O(1)$ |
std::pair<PersistentOrderedMultiset, PersistentOrderedMultiset> split(const T& key) const |
Returns {less, greater_equal} without changing this version. |
$O(\log N)$ |
PersistentOrderedMultiset merge(const PersistentOrderedMultiset& other) const |
Returns the union without changing either version. Requires every key in *this to be smaller than every key in other. |
$O(\log(N + M))$ |
std::vector<T> to_vector() const |
Returns all elements in sorted order, including duplicates. | $O(N)$ |
Here $F$ is the number of nodes that become unreachable. Destruction and assignment release roots automatically.
Example
#include "ds/bst/persistent_ordered_multiset.hpp"
#include <iostream>
int main() {
m1une::ds::PersistentOrderedMultiset<int> a;
auto b = a.insert(3).insert(1).insert(3);
auto c = b.erase_one(3);
auto [small, large] = b.split(3);
auto joined = small.merge(large);
std::cout << a.size() << "\n"; // 0
std::cout << b.count(3) << "\n"; // 2
std::cout << c.count(3) << "\n"; // 1
}
Depends on
Required by
Verified with
- verify/ds/bst/persistent_ordered_multiset.test.cpp
- verify/ds/bst/persistent_ordered_set.test.cpp
- verify/ds/persistent_cow.test.cpp
- verify/ds/persistent_release.test.cpp
- verify/ds/persistent_release.test.cpp
Code
#ifndef M1UNE_PERSISTENT_ORDERED_MULTISET_HPP
#define M1UNE_PERSISTENT_ORDERED_MULTISET_HPP 1
#include <cassert>
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <utility>
#include <vector>
#include "../detail/persistent_binary_node_pool.hpp"
namespace m1une {
namespace ds {
template <typename T, typename Compare>
struct PersistentOrderedSet;
template <typename T, typename Compare = std::less<T>>
struct PersistentOrderedMultiset {
private:
friend struct PersistentOrderedSet<T, Compare>;
struct Node {
T key;
int count;
int size;
int distinct_size;
int rank_color;
int l;
int r;
int min_leaf;
int max_leaf;
Node(T value, int multiplicity, int maximum)
: key(std::move(value)),
count(multiplicity),
size(multiplicity),
distinct_size(1),
rank_color(1),
l(-1),
r(-1),
min_leaf(maximum),
max_leaf(maximum) {}
Node(T separator, int subtree_size, int left_size, int unique_count, int node_rank,
int left, int right, int minimum, int maximum, bool is_black)
: key(std::move(separator)),
count(left_size),
size(subtree_size),
distinct_size(unique_count),
rank_color(node_rank * 2 + int(is_black)),
l(left),
r(right),
min_leaf(minimum),
max_leaf(maximum) {}
};
using Pool = detail::PersistentBinaryNodePool<Node>;
inline static Pool pool;
int root;
Compare comp;
static int subtree_size(int t) { return t == -1 ? 0 : pool[t].size; }
static int subtree_distinct_size(int t) { return t == -1 ? 0 : pool[t].distinct_size; }
static int node_rank(int t) { return pool[t].rank_color >> 1; }
static bool is_black(int t) { return (pool[t].rank_color & 1) != 0; }
static bool is_leaf(int t) { return pool[t].l == -1; }
bool equal(const T& a, const T& b) const {
return !comp(a, b) && !comp(b, a);
}
static int make_leaf(T key, int count) {
const int id = pool.next_index();
return pool.emplace(std::move(key), count, id);
}
static int make_node(int l, int r, bool black) {
assert(l != -1 && r != -1);
const int rank = node_rank(l) + int(is_black(l));
assert(rank == node_rank(r) + int(is_black(r)));
return pool.emplace(pool[pool[l].max_leaf].key,
subtree_size(l) + subtree_size(r),
subtree_size(l),
subtree_distinct_size(l) + subtree_distinct_size(r),
rank, l, r, pool[l].min_leaf, pool[r].max_leaf,
black);
}
static int as_root(int t) {
if (t == -1 || is_black(t)) return t;
return make_node(pool[t].l, pool[t].r, true);
}
static int merge_sub(int a, int b) {
assert(a != -1 && b != -1);
if (node_rank(a) < node_rank(b)) {
const Node& right = pool[b];
int c = merge_sub(a, right.l);
if (is_black(b) && !is_black(c) && !is_black(pool[c].l)) {
const Node& middle = pool[c];
if (is_black(right.r)) {
return make_node(middle.l,
make_node(middle.r, right.r, false),
true);
}
const Node& far = pool[right.r];
return make_node(make_node(middle.l, middle.r, true),
make_node(far.l, far.r, true),
false);
}
return make_node(c, right.r, is_black(b));
}
if (node_rank(a) > node_rank(b)) {
const Node& left = pool[a];
int c = merge_sub(left.r, b);
if (is_black(a) && !is_black(c) && !is_black(pool[c].r)) {
const Node& middle = pool[c];
if (is_black(left.l)) {
return make_node(make_node(left.l, middle.l, false),
middle.r, true);
}
const Node& far = pool[left.l];
return make_node(make_node(far.l, far.r, true),
make_node(middle.l, middle.r, true),
false);
}
return make_node(left.l, c, is_black(a));
}
return make_node(a, b, false);
}
static int merge_nodes(int a, int b) {
if (a == -1 || b == -1) return a == -1 ? b : a;
return as_root(merge_sub(as_root(a), as_root(b)));
}
std::pair<int, int> split_nodes(int t, const T& key) const {
if (t == -1) return {-1, -1};
const Node& node = pool[t];
if (is_leaf(t)) return comp(node.key, key) ? std::pair{t, -1} : std::pair{-1, t};
if (comp(node.key, key)) {
auto [l, r] = split_nodes(node.r, key);
return {merge_nodes(as_root(node.l), l), r};
}
auto [l, r] = split_nodes(node.l, key);
return {l, merge_nodes(r, as_root(node.r))};
}
int change_count_impl(int t, const T& key, int delta, int& old_count) const {
if (t == -1) return -1;
const Node& node = pool[t];
if (is_leaf(t)) {
if (!equal(node.key, key)) return t;
old_count = node.count;
return node.count + delta == 0 ? t : make_leaf(node.key, node.count + delta);
}
int child;
if (!comp(node.key, key)) {
child = change_count_impl(node.l, key, delta, old_count);
if (old_count == 0 || old_count + delta == 0) return t;
return make_node(child, node.r, is_black(t));
}
child = change_count_impl(node.r, key, delta, old_count);
if (old_count == 0 || old_count + delta == 0) return t;
return make_node(node.l, child, is_black(t));
}
int change_count_inplace(int t, const T& key, int delta) const {
t = pool.clone_if_shared(t);
if (is_leaf(t)) {
assert(equal(pool[t].key, key));
assert(pool[t].count + delta > 0);
pool[t].count += delta;
pool[t].size += delta;
return t;
}
if (!comp(pool[t].key, key)) {
int child = change_count_inplace(pool[t].l, key, delta);
pool.replace(pool[t].l, child);
} else {
int child = change_count_inplace(pool[t].r, key, delta);
pool.replace(pool[t].r, child);
}
Node& node = pool[t];
node.count = subtree_size(node.l);
node.size = node.count + subtree_size(node.r);
return t;
}
int count_impl(int t, const T& key) const {
if (t == -1) return 0;
while (!is_leaf(t)) {
t = !comp(pool[t].key, key) ? pool[t].l : pool[t].r;
}
return equal(pool[t].key, key) ? pool[t].count : 0;
}
const T* kth_impl(int t, int k) const {
while (!is_leaf(t)) {
const int left_size = pool[t].count;
if (k < left_size) {
t = pool[t].l;
} else {
k -= left_size;
t = pool[t].r;
}
}
return &pool[t].key;
}
int order_of_key_impl(int t, const T& key, bool upper) const {
int result = 0;
while (t != -1 && !is_leaf(t)) {
const Node& node = pool[t];
const T& separator = node.key;
const bool take_left = upper ? !comp(key, separator) : comp(separator, key);
if (take_left) {
result += node.count;
t = node.r;
} else {
t = node.l;
}
}
if (t != -1) {
const bool take_leaf = upper ? !comp(key, pool[t].key) : comp(pool[t].key, key);
if (take_leaf) result += pool[t].count;
}
return result;
}
const T* lower_bound_impl(int t, const T& key, bool strict) const {
const T* result = nullptr;
while (t != -1) {
const Node& node = pool[t];
if (is_leaf(t)) {
const bool candidate = strict ? comp(key, node.key) : !comp(node.key, key);
return candidate ? &node.key : result;
}
const T& separator = node.key;
const bool go_left = strict ? comp(key, separator) : !comp(separator, key);
if (go_left) {
result = &pool[pool[node.r].min_leaf].key;
t = node.l;
} else {
t = node.r;
}
}
return result;
}
const T* max_less_impl(int t, const T& key, bool strict) const {
const T* result = nullptr;
while (t != -1) {
const Node& node = pool[t];
if (is_leaf(t)) {
const bool candidate = strict ? comp(node.key, key) : !comp(key, node.key);
return candidate ? &node.key : result;
}
const T& separator = node.key;
const bool take_left = strict ? comp(separator, key) : !comp(key, separator);
if (take_left) {
result = &separator;
t = node.r;
} else {
t = node.l;
}
}
return result;
}
static void dump_impl(int t, std::vector<T>& result) {
if (t == -1) return;
const Node& node = pool[t];
if (is_leaf(t)) {
for (int i = 0; i < node.count; ++i) result.push_back(node.key);
return;
}
dump_impl(node.l, result);
dump_impl(node.r, result);
}
static std::pair<int, int> pop_min(int t) {
assert(t != -1);
const Node& node = pool[t];
if (is_leaf(t)) return {t, -1};
auto [minimum, rest] = pop_min(node.l);
return {minimum, merge_nodes(rest, as_root(node.r))};
}
PersistentOrderedMultiset(int node, Compare compare) : root(node), comp(std::move(compare)) {
pool.retain(root);
}
PersistentOrderedMultiset make_version(int node) const {
PersistentOrderedMultiset result(node, comp);
pool.discard_unreferenced();
return result;
}
public:
explicit PersistentOrderedMultiset(Compare compare) : root(-1), comp(std::move(compare)) {}
PersistentOrderedMultiset() : PersistentOrderedMultiset(Compare()) {}
PersistentOrderedMultiset(std::initializer_list<T> init, Compare compare = Compare())
: PersistentOrderedMultiset(std::move(compare)) {
for (const T& x : init) *this = insert(x);
}
template <typename Iterator>
PersistentOrderedMultiset(Iterator first, Iterator last, Compare compare = Compare())
: PersistentOrderedMultiset(std::move(compare)) {
while (first != last) *this = insert(*first++);
}
PersistentOrderedMultiset(const PersistentOrderedMultiset& other)
: root(other.root), comp(other.comp) {
pool.retain(root);
}
PersistentOrderedMultiset(PersistentOrderedMultiset&& other)
: root(other.root), comp(std::move(other.comp)) {
other.root = -1;
}
PersistentOrderedMultiset& operator=(const PersistentOrderedMultiset& other) {
if (this == &other) return *this;
pool.retain(other.root);
pool.release(root);
root = other.root;
comp = other.comp;
return *this;
}
PersistentOrderedMultiset& operator=(PersistentOrderedMultiset&& other) {
if (this == &other) return *this;
pool.release(root);
root = other.root;
comp = std::move(other.comp);
other.root = -1;
return *this;
}
~PersistentOrderedMultiset() { pool.release(root); }
int size() const { return subtree_size(root); }
int unique_size() const { return subtree_distinct_size(root); }
bool empty() const { return root == -1; }
void release() { pool.release(std::exchange(root, -1)); }
std::size_t node_count() const { return pool.size(); }
PersistentOrderedMultiset clear() const { return make_version(-1); }
PersistentOrderedMultiset insert(T key, int multiplicity = 1) const {
assert(multiplicity > 0);
int old_count = 0;
const int changed_root = change_count_impl(root, key, multiplicity, old_count);
if (old_count != 0) {
return make_version(changed_root);
}
auto [l, r] = split_nodes(root, key);
return make_version(merge_nodes(merge_nodes(l, make_leaf(std::move(key), multiplicity)), r));
}
void insert_inplace(T key, int multiplicity = 1) {
assert(multiplicity > 0);
if (!contains(key)) {
*this = insert(std::move(key), multiplicity);
return;
}
int next_root = change_count_inplace(root, key, multiplicity);
pool.replace(root, next_root);
pool.discard_unreferenced();
}
private:
PersistentOrderedMultiset insert_unique(T key) const {
if (contains(key)) return *this;
auto [l, r] = split_nodes(root, key);
return make_version(merge_nodes(merge_nodes(l, make_leaf(std::move(key), 1)), r));
}
public:
PersistentOrderedMultiset erase_one(const T& key) const {
int old_count = 0;
const int changed_root = change_count_impl(root, key, -1, old_count);
if (old_count == 0) return *this;
if (old_count > 1) return make_version(changed_root);
auto [l, r] = split_nodes(root, key);
auto [discarded, rest] = pop_min(r);
assert(equal(pool[discarded].key, key));
return make_version(merge_nodes(l, rest));
}
PersistentOrderedMultiset erase(const T& key) const { return erase_one(key); }
bool erase_one_inplace(const T& key) {
int old_count = count(key);
if (old_count == 0) return false;
if (old_count == 1) {
*this = erase_one(key);
return true;
}
int next_root = change_count_inplace(root, key, -1);
pool.replace(root, next_root);
pool.discard_unreferenced();
return true;
}
bool erase_inplace(const T& key) { return erase_one_inplace(key); }
PersistentOrderedMultiset erase_all(const T& key) const {
const int old_count = count(key);
if (old_count == 0) return *this;
auto [l, r] = split_nodes(root, key);
auto [discarded, rest] = pop_min(r);
assert(equal(pool[discarded].key, key));
return make_version(merge_nodes(l, rest));
}
bool erase_all_inplace(const T& key) {
if (!contains(key)) return false;
*this = erase_all(key);
return true;
}
bool contains(const T& key) const { return count(key) > 0; }
int count(const T& key) const { return count_impl(root, key); }
const T* find_by_order(int k) const {
assert(0 <= k && k < size());
return kth_impl(root, k);
}
T kth(int k) const { return *find_by_order(k); }
int order_of_key(const T& key) const { return order_of_key_impl(root, key, false); }
int count_less(const T& key) const { return order_of_key(key); }
int count_less_equal(const T& key) const { return order_of_key_impl(root, key, true); }
int count_greater(const T& key) const { return size() - count_less_equal(key); }
int count_greater_equal(const T& key) const { return size() - count_less(key); }
const T* lower_bound(const T& key) const { return lower_bound_impl(root, key, false); }
const T* upper_bound(const T& key) const { return lower_bound_impl(root, key, true); }
const T* min_ge(const T& key) const { return lower_bound(key); }
const T* min_gt(const T& key) const { return upper_bound(key); }
const T* max_le(const T& key) const { return max_less_impl(root, key, false); }
const T* max_lt(const T& key) const { return max_less_impl(root, key, true); }
const T* min() const { return empty() ? nullptr : &pool[pool[root].min_leaf].key; }
const T* max() const { return empty() ? nullptr : &pool[pool[root].max_leaf].key; }
std::pair<PersistentOrderedMultiset, PersistentOrderedMultiset> split(const T& key) const {
auto [l, r] = split_nodes(root, key);
PersistentOrderedMultiset left(l, comp);
PersistentOrderedMultiset right(r, comp);
pool.discard_unreferenced();
return {std::move(left), std::move(right)};
}
PersistentOrderedMultiset merge(const PersistentOrderedMultiset& other) const {
assert(empty() || other.empty() || comp(*max(), *other.min()));
return make_version(merge_nodes(root, other.root));
}
std::vector<T> to_vector() const {
std::vector<T> result;
result.reserve(size());
dump_impl(root, result);
return result;
}
};
} // namespace ds
} // namespace m1une
#endif // M1UNE_PERSISTENT_ORDERED_MULTISET_HPP#line 1 "ds/bst/persistent_ordered_multiset.hpp"
#include <cassert>
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <utility>
#include <vector>
#line 1 "ds/detail/persistent_binary_node_pool.hpp"
#line 6 "ds/detail/persistent_binary_node_pool.hpp"
#include <deque>
#include <limits>
#include <optional>
#line 11 "ds/detail/persistent_binary_node_pool.hpp"
namespace m1une {
namespace ds {
namespace detail {
// Node must have integer `l` and `r` members. New nodes initially have no
// owner; discard_unreferenced() removes temporary path-copy nodes after the
// result roots have been retained.
template <class Node, int null_node = -1>
struct PersistentBinaryNodePool {
private:
std::deque<std::optional<Node>> _nodes;
std::vector<int> _references;
std::vector<int> _next_free;
std::vector<int> _unowned;
int _first_free = -1;
std::size_t _live_nodes = 0;
void release_zero(int node) {
assert(node != null_node && _nodes[node].has_value());
int left = (*_nodes[node]).l;
int right = (*_nodes[node]).r;
_nodes[node].reset();
_next_free[node] = _first_free;
_first_free = node;
--_live_nodes;
if (left != null_node && --_references[left] == 0) release_zero(left);
if (right != null_node && --_references[right] == 0) release_zero(right);
}
public:
PersistentBinaryNodePool() {
if constexpr (null_node == 0) {
_nodes.emplace_back();
_references.push_back(0);
_next_free.push_back(-1);
}
}
Node& operator[](int node) {
assert(node != null_node && _nodes[node].has_value());
return *_nodes[node];
}
const Node& operator[](int node) const {
assert(node != null_node && _nodes[node].has_value());
return *_nodes[node];
}
template <class... Args>
int emplace(Args&&... args) {
int result;
if (_first_free == -1) {
assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
result = int(_nodes.size());
_nodes.emplace_back(std::in_place, std::forward<Args>(args)...);
_references.push_back(0);
_next_free.push_back(-1);
} else {
result = _first_free;
_first_free = _next_free[result];
_nodes[result].emplace(std::forward<Args>(args)...);
_references[result] = 0;
}
retain((*_nodes[result]).l);
retain((*_nodes[result]).r);
_unowned.push_back(result);
++_live_nodes;
return result;
}
void retain(int node) {
if (node != null_node) {
assert(_nodes[node].has_value());
++_references[node];
}
}
void release(int node) {
if (node == null_node) return;
assert(_nodes[node].has_value() && _references[node] > 0);
if (--_references[node] == 0) release_zero(node);
}
bool unique(int node) const {
return node == null_node || _references[node] == 1;
}
int clone(int node) {
assert(node != null_node && _nodes[node].has_value());
return emplace(*_nodes[node]);
}
// Returns node itself when it has one owner, otherwise an unowned clone.
// A returned clone becomes owned when a root or parent edge retains it.
int clone_if_shared(int node) {
if (unique(node)) return node;
return clone(node);
}
void replace(int& edge, int node) {
if (edge == node) return;
retain(node);
int old = edge;
edge = node;
release(old);
}
void discard_unreferenced() {
while (!_unowned.empty()) {
int node = _unowned.back();
_unowned.pop_back();
if (_nodes[node].has_value() && _references[node] == 0) release_zero(node);
}
}
void reserve(std::size_t) {}
int next_index() const { return _first_free == -1 ? int(_nodes.size()) : _first_free; }
std::size_t size() const { return _live_nodes; }
};
} // namespace detail
} // namespace ds
} // namespace m1une
#line 12 "ds/bst/persistent_ordered_multiset.hpp"
namespace m1une {
namespace ds {
template <typename T, typename Compare>
struct PersistentOrderedSet;
template <typename T, typename Compare = std::less<T>>
struct PersistentOrderedMultiset {
private:
friend struct PersistentOrderedSet<T, Compare>;
struct Node {
T key;
int count;
int size;
int distinct_size;
int rank_color;
int l;
int r;
int min_leaf;
int max_leaf;
Node(T value, int multiplicity, int maximum)
: key(std::move(value)),
count(multiplicity),
size(multiplicity),
distinct_size(1),
rank_color(1),
l(-1),
r(-1),
min_leaf(maximum),
max_leaf(maximum) {}
Node(T separator, int subtree_size, int left_size, int unique_count, int node_rank,
int left, int right, int minimum, int maximum, bool is_black)
: key(std::move(separator)),
count(left_size),
size(subtree_size),
distinct_size(unique_count),
rank_color(node_rank * 2 + int(is_black)),
l(left),
r(right),
min_leaf(minimum),
max_leaf(maximum) {}
};
using Pool = detail::PersistentBinaryNodePool<Node>;
inline static Pool pool;
int root;
Compare comp;
static int subtree_size(int t) { return t == -1 ? 0 : pool[t].size; }
static int subtree_distinct_size(int t) { return t == -1 ? 0 : pool[t].distinct_size; }
static int node_rank(int t) { return pool[t].rank_color >> 1; }
static bool is_black(int t) { return (pool[t].rank_color & 1) != 0; }
static bool is_leaf(int t) { return pool[t].l == -1; }
bool equal(const T& a, const T& b) const {
return !comp(a, b) && !comp(b, a);
}
static int make_leaf(T key, int count) {
const int id = pool.next_index();
return pool.emplace(std::move(key), count, id);
}
static int make_node(int l, int r, bool black) {
assert(l != -1 && r != -1);
const int rank = node_rank(l) + int(is_black(l));
assert(rank == node_rank(r) + int(is_black(r)));
return pool.emplace(pool[pool[l].max_leaf].key,
subtree_size(l) + subtree_size(r),
subtree_size(l),
subtree_distinct_size(l) + subtree_distinct_size(r),
rank, l, r, pool[l].min_leaf, pool[r].max_leaf,
black);
}
static int as_root(int t) {
if (t == -1 || is_black(t)) return t;
return make_node(pool[t].l, pool[t].r, true);
}
static int merge_sub(int a, int b) {
assert(a != -1 && b != -1);
if (node_rank(a) < node_rank(b)) {
const Node& right = pool[b];
int c = merge_sub(a, right.l);
if (is_black(b) && !is_black(c) && !is_black(pool[c].l)) {
const Node& middle = pool[c];
if (is_black(right.r)) {
return make_node(middle.l,
make_node(middle.r, right.r, false),
true);
}
const Node& far = pool[right.r];
return make_node(make_node(middle.l, middle.r, true),
make_node(far.l, far.r, true),
false);
}
return make_node(c, right.r, is_black(b));
}
if (node_rank(a) > node_rank(b)) {
const Node& left = pool[a];
int c = merge_sub(left.r, b);
if (is_black(a) && !is_black(c) && !is_black(pool[c].r)) {
const Node& middle = pool[c];
if (is_black(left.l)) {
return make_node(make_node(left.l, middle.l, false),
middle.r, true);
}
const Node& far = pool[left.l];
return make_node(make_node(far.l, far.r, true),
make_node(middle.l, middle.r, true),
false);
}
return make_node(left.l, c, is_black(a));
}
return make_node(a, b, false);
}
static int merge_nodes(int a, int b) {
if (a == -1 || b == -1) return a == -1 ? b : a;
return as_root(merge_sub(as_root(a), as_root(b)));
}
std::pair<int, int> split_nodes(int t, const T& key) const {
if (t == -1) return {-1, -1};
const Node& node = pool[t];
if (is_leaf(t)) return comp(node.key, key) ? std::pair{t, -1} : std::pair{-1, t};
if (comp(node.key, key)) {
auto [l, r] = split_nodes(node.r, key);
return {merge_nodes(as_root(node.l), l), r};
}
auto [l, r] = split_nodes(node.l, key);
return {l, merge_nodes(r, as_root(node.r))};
}
int change_count_impl(int t, const T& key, int delta, int& old_count) const {
if (t == -1) return -1;
const Node& node = pool[t];
if (is_leaf(t)) {
if (!equal(node.key, key)) return t;
old_count = node.count;
return node.count + delta == 0 ? t : make_leaf(node.key, node.count + delta);
}
int child;
if (!comp(node.key, key)) {
child = change_count_impl(node.l, key, delta, old_count);
if (old_count == 0 || old_count + delta == 0) return t;
return make_node(child, node.r, is_black(t));
}
child = change_count_impl(node.r, key, delta, old_count);
if (old_count == 0 || old_count + delta == 0) return t;
return make_node(node.l, child, is_black(t));
}
int change_count_inplace(int t, const T& key, int delta) const {
t = pool.clone_if_shared(t);
if (is_leaf(t)) {
assert(equal(pool[t].key, key));
assert(pool[t].count + delta > 0);
pool[t].count += delta;
pool[t].size += delta;
return t;
}
if (!comp(pool[t].key, key)) {
int child = change_count_inplace(pool[t].l, key, delta);
pool.replace(pool[t].l, child);
} else {
int child = change_count_inplace(pool[t].r, key, delta);
pool.replace(pool[t].r, child);
}
Node& node = pool[t];
node.count = subtree_size(node.l);
node.size = node.count + subtree_size(node.r);
return t;
}
int count_impl(int t, const T& key) const {
if (t == -1) return 0;
while (!is_leaf(t)) {
t = !comp(pool[t].key, key) ? pool[t].l : pool[t].r;
}
return equal(pool[t].key, key) ? pool[t].count : 0;
}
const T* kth_impl(int t, int k) const {
while (!is_leaf(t)) {
const int left_size = pool[t].count;
if (k < left_size) {
t = pool[t].l;
} else {
k -= left_size;
t = pool[t].r;
}
}
return &pool[t].key;
}
int order_of_key_impl(int t, const T& key, bool upper) const {
int result = 0;
while (t != -1 && !is_leaf(t)) {
const Node& node = pool[t];
const T& separator = node.key;
const bool take_left = upper ? !comp(key, separator) : comp(separator, key);
if (take_left) {
result += node.count;
t = node.r;
} else {
t = node.l;
}
}
if (t != -1) {
const bool take_leaf = upper ? !comp(key, pool[t].key) : comp(pool[t].key, key);
if (take_leaf) result += pool[t].count;
}
return result;
}
const T* lower_bound_impl(int t, const T& key, bool strict) const {
const T* result = nullptr;
while (t != -1) {
const Node& node = pool[t];
if (is_leaf(t)) {
const bool candidate = strict ? comp(key, node.key) : !comp(node.key, key);
return candidate ? &node.key : result;
}
const T& separator = node.key;
const bool go_left = strict ? comp(key, separator) : !comp(separator, key);
if (go_left) {
result = &pool[pool[node.r].min_leaf].key;
t = node.l;
} else {
t = node.r;
}
}
return result;
}
const T* max_less_impl(int t, const T& key, bool strict) const {
const T* result = nullptr;
while (t != -1) {
const Node& node = pool[t];
if (is_leaf(t)) {
const bool candidate = strict ? comp(node.key, key) : !comp(key, node.key);
return candidate ? &node.key : result;
}
const T& separator = node.key;
const bool take_left = strict ? comp(separator, key) : !comp(key, separator);
if (take_left) {
result = &separator;
t = node.r;
} else {
t = node.l;
}
}
return result;
}
static void dump_impl(int t, std::vector<T>& result) {
if (t == -1) return;
const Node& node = pool[t];
if (is_leaf(t)) {
for (int i = 0; i < node.count; ++i) result.push_back(node.key);
return;
}
dump_impl(node.l, result);
dump_impl(node.r, result);
}
static std::pair<int, int> pop_min(int t) {
assert(t != -1);
const Node& node = pool[t];
if (is_leaf(t)) return {t, -1};
auto [minimum, rest] = pop_min(node.l);
return {minimum, merge_nodes(rest, as_root(node.r))};
}
PersistentOrderedMultiset(int node, Compare compare) : root(node), comp(std::move(compare)) {
pool.retain(root);
}
PersistentOrderedMultiset make_version(int node) const {
PersistentOrderedMultiset result(node, comp);
pool.discard_unreferenced();
return result;
}
public:
explicit PersistentOrderedMultiset(Compare compare) : root(-1), comp(std::move(compare)) {}
PersistentOrderedMultiset() : PersistentOrderedMultiset(Compare()) {}
PersistentOrderedMultiset(std::initializer_list<T> init, Compare compare = Compare())
: PersistentOrderedMultiset(std::move(compare)) {
for (const T& x : init) *this = insert(x);
}
template <typename Iterator>
PersistentOrderedMultiset(Iterator first, Iterator last, Compare compare = Compare())
: PersistentOrderedMultiset(std::move(compare)) {
while (first != last) *this = insert(*first++);
}
PersistentOrderedMultiset(const PersistentOrderedMultiset& other)
: root(other.root), comp(other.comp) {
pool.retain(root);
}
PersistentOrderedMultiset(PersistentOrderedMultiset&& other)
: root(other.root), comp(std::move(other.comp)) {
other.root = -1;
}
PersistentOrderedMultiset& operator=(const PersistentOrderedMultiset& other) {
if (this == &other) return *this;
pool.retain(other.root);
pool.release(root);
root = other.root;
comp = other.comp;
return *this;
}
PersistentOrderedMultiset& operator=(PersistentOrderedMultiset&& other) {
if (this == &other) return *this;
pool.release(root);
root = other.root;
comp = std::move(other.comp);
other.root = -1;
return *this;
}
~PersistentOrderedMultiset() { pool.release(root); }
int size() const { return subtree_size(root); }
int unique_size() const { return subtree_distinct_size(root); }
bool empty() const { return root == -1; }
void release() { pool.release(std::exchange(root, -1)); }
std::size_t node_count() const { return pool.size(); }
PersistentOrderedMultiset clear() const { return make_version(-1); }
PersistentOrderedMultiset insert(T key, int multiplicity = 1) const {
assert(multiplicity > 0);
int old_count = 0;
const int changed_root = change_count_impl(root, key, multiplicity, old_count);
if (old_count != 0) {
return make_version(changed_root);
}
auto [l, r] = split_nodes(root, key);
return make_version(merge_nodes(merge_nodes(l, make_leaf(std::move(key), multiplicity)), r));
}
void insert_inplace(T key, int multiplicity = 1) {
assert(multiplicity > 0);
if (!contains(key)) {
*this = insert(std::move(key), multiplicity);
return;
}
int next_root = change_count_inplace(root, key, multiplicity);
pool.replace(root, next_root);
pool.discard_unreferenced();
}
private:
PersistentOrderedMultiset insert_unique(T key) const {
if (contains(key)) return *this;
auto [l, r] = split_nodes(root, key);
return make_version(merge_nodes(merge_nodes(l, make_leaf(std::move(key), 1)), r));
}
public:
PersistentOrderedMultiset erase_one(const T& key) const {
int old_count = 0;
const int changed_root = change_count_impl(root, key, -1, old_count);
if (old_count == 0) return *this;
if (old_count > 1) return make_version(changed_root);
auto [l, r] = split_nodes(root, key);
auto [discarded, rest] = pop_min(r);
assert(equal(pool[discarded].key, key));
return make_version(merge_nodes(l, rest));
}
PersistentOrderedMultiset erase(const T& key) const { return erase_one(key); }
bool erase_one_inplace(const T& key) {
int old_count = count(key);
if (old_count == 0) return false;
if (old_count == 1) {
*this = erase_one(key);
return true;
}
int next_root = change_count_inplace(root, key, -1);
pool.replace(root, next_root);
pool.discard_unreferenced();
return true;
}
bool erase_inplace(const T& key) { return erase_one_inplace(key); }
PersistentOrderedMultiset erase_all(const T& key) const {
const int old_count = count(key);
if (old_count == 0) return *this;
auto [l, r] = split_nodes(root, key);
auto [discarded, rest] = pop_min(r);
assert(equal(pool[discarded].key, key));
return make_version(merge_nodes(l, rest));
}
bool erase_all_inplace(const T& key) {
if (!contains(key)) return false;
*this = erase_all(key);
return true;
}
bool contains(const T& key) const { return count(key) > 0; }
int count(const T& key) const { return count_impl(root, key); }
const T* find_by_order(int k) const {
assert(0 <= k && k < size());
return kth_impl(root, k);
}
T kth(int k) const { return *find_by_order(k); }
int order_of_key(const T& key) const { return order_of_key_impl(root, key, false); }
int count_less(const T& key) const { return order_of_key(key); }
int count_less_equal(const T& key) const { return order_of_key_impl(root, key, true); }
int count_greater(const T& key) const { return size() - count_less_equal(key); }
int count_greater_equal(const T& key) const { return size() - count_less(key); }
const T* lower_bound(const T& key) const { return lower_bound_impl(root, key, false); }
const T* upper_bound(const T& key) const { return lower_bound_impl(root, key, true); }
const T* min_ge(const T& key) const { return lower_bound(key); }
const T* min_gt(const T& key) const { return upper_bound(key); }
const T* max_le(const T& key) const { return max_less_impl(root, key, false); }
const T* max_lt(const T& key) const { return max_less_impl(root, key, true); }
const T* min() const { return empty() ? nullptr : &pool[pool[root].min_leaf].key; }
const T* max() const { return empty() ? nullptr : &pool[pool[root].max_leaf].key; }
std::pair<PersistentOrderedMultiset, PersistentOrderedMultiset> split(const T& key) const {
auto [l, r] = split_nodes(root, key);
PersistentOrderedMultiset left(l, comp);
PersistentOrderedMultiset right(r, comp);
pool.discard_unreferenced();
return {std::move(left), std::move(right)};
}
PersistentOrderedMultiset merge(const PersistentOrderedMultiset& other) const {
assert(empty() || other.empty() || comp(*max(), *other.min()));
return make_version(merge_nodes(root, other.root));
}
std::vector<T> to_vector() const {
std::vector<T> result;
result.reserve(size());
dump_impl(root, result);
return result;
}
};
} // namespace ds
} // namespace m1une