sortable_segment_tree.hpp¶
Maintain a sequence of distinct integer keys and monoid values under point replacement, ordered range product, and sorting a range by key. Each maximal already-sorted block is stored as a sparse segment tree over key space, containing both forward and backward products. Sorting joins all blocks in the range; splitting a block by sequence rank restores query boundaries. A fast set tracks block starts and an outer segment tree stores one aggregate per block. Since an operation creates only O(1) boundaries, the total number of block splits and merges is linear in the operation count; periodic rebuilding bounds the persistent split-node storage.
Verified by point_set_range_sort_range_composite.
维护序列的单点修改、区间升降序排序和区间复合查询；适合排序后仍需按顺序聚合函数或矩阵的题目。
Implementation¶
#ifndef NOYA_SORTABLE_SEGMENT_TREE_HPP
#define NOYA_SORTABLE_SEGMENT_TREE_HPP 1
/// @complexity Time: O(n log K) construction; a sequence of q point updates,
/// range products, and range sorts takes O((n + q)(log n + log K)) amortized,
/// where keys lie in [0, K). Space: O(n log K).
#include "noya/fastset.hpp"
#include "noya/segtree.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
/// @brief Maintain a sequence of distinct integer keys and monoid values under
/// point replacement, ordered range product, and sorting a range by key. Each
/// maximal already-sorted block is stored as a sparse segment tree over key
/// space, containing both forward and backward products. Sorting joins all
/// blocks in the range; splitting a block by sequence rank restores query
/// boundaries. A fast set tracks block starts and an outer segment tree stores
/// one aggregate per block. Since an operation creates only O(1) boundaries,
/// the total number of block splits and merges is linear in the operation
/// count; periodic rebuilding bounds the persistent split-node storage.
template <class Monoid> class sortable_segment_tree {
public:
using value_type = typename Monoid::value_type;
private:
struct node {
value_type forward;
value_type backward;
int size = 1;
int left = -1;
int right = -1;
};
int size_ = 0;
int key_count_ = 0;
int key_log_ = 0;
std::size_t rebuild_limit_ = 0;
fast_set block_starts_;
segtree<Monoid> block_products_;
std::vector<bool> reversed_;
std::vector<int> roots_;
std::vector<node> nodes_;
public:
sortable_segment_tree() = default;
sortable_segment_tree(int key_count, const std::vector<int> &keys,
const std::vector<value_type> &values) {
build(key_count, keys, values);
}
void build(int key_count, const std::vector<int> &keys,
const std::vector<value_type> &values) {
assert(!keys.empty());
assert(keys.size() == values.size());
assert(key_count > 0);
size_ = int(keys.size());
key_count_ = key_count;
key_log_ = 0;
for (int range = 1; range < key_count_;) {
range <<= 1;
key_log_++;
}
rebuild_limit_ = std::max<std::size_t>(
4096, std::size_t(size_) * std::size_t(key_log_ + 1) * 2 + 1024);
initialize(keys, values);
}
int size() const { return size_; }
void set(int position, int key, const value_type &value) {
assert(0 <= position && position < size_);
assert(0 <= key && key < key_count_);
make_boundary(position);
make_boundary(position + 1);
maybe_rebuild();
reversed_[position] = false;
roots_[position] = make_node();
set_key(roots_[position], 0, key_count_, key, value);
block_products_.set(position, value);
}
value_type prod(int left, int right) {
assert(0 <= left && left <= right && right <= size_);
if (left == right) {
return Monoid::unit();
}
make_boundary(left);
make_boundary(right);
return block_products_.prod(left, right);
}
value_type all_prod() const { return block_products_.all_prod(); }
void sort_ascending(int left, int right) {
assert(0 <= left && left <= right && right <= size_);
if (left == right) {
return;
}
make_boundary(left);
make_boundary(right);
while (true) {
maybe_rebuild();
int next_start = block_starts_.next(left + 1);
if (next_start == right) {
break;
}
roots_[left] = merge(roots_[left], roots_[next_start]);
block_starts_.erase(next_start);
block_products_.set(next_start, Monoid::unit());
}
reversed_[left] = false;
block_products_.set(left, forward_product(roots_[left]));
}
void sort_descending(int left, int right) {
assert(0 <= left && left <= right && right <= size_);
if (left == right) {
return;
}
sort_ascending(left, right);
reversed_[left] = true;
block_products_.set(left, backward_product(roots_[left]));
}
private:
int node_size(int current) const {
return current == -1 ? 0 : nodes_[current].size;
}
value_type forward_product(int current) const {
return current == -1 ? Monoid::unit() : nodes_[current].forward;
}
value_type backward_product(int current) const {
return current == -1 ? Monoid::unit() : nodes_[current].backward;
}
int make_node(value_type value = Monoid::unit()) {
nodes_.push_back({value, value, 1, -1, -1});
return int(nodes_.size()) - 1;
}
void pull(int current) {
int left = nodes_[current].left;
int right = nodes_[current].right;
if (left == -1 && right == -1) {
return;
}
nodes_[current].size = node_size(left) + node_size(right);
nodes_[current].forward =
Monoid::op(forward_product(left), forward_product(right));
nodes_[current].backward =
Monoid::op(backward_product(right), backward_product(left));
}
void set_key(int current, int low, int high, int key,
const value_type &value) {
if (low + 1 == high) {
nodes_[current].forward = nodes_[current].backward = value;
return;
}
int middle = (low + high) / 2;
if (key < middle) {
if (nodes_[current].left == -1) {
nodes_[current].left = make_node();
}
set_key(nodes_[current].left, low, middle, key, value);
} else {
if (nodes_[current].right == -1) {
nodes_[current].right = make_node();
}
set_key(nodes_[current].right, middle, high, key, value);
}
pull(current);
}
int merge(int first, int second) {
if (first == -1 || second == -1) {
return first == -1 ? second : first;
}
nodes_[first].left = merge(nodes_[first].left, nodes_[second].left);
nodes_[first].right = merge(nodes_[first].right, nodes_[second].right);
pull(first);
return first;
}
std::pair<int, int> split(int current, int left_size) {
assert(current != -1);
assert(0 <= left_size && left_size <= nodes_[current].size);
if (left_size == 0) {
return {-1, current};
}
if (left_size == nodes_[current].size) {
return {current, -1};
}
int right_part = make_node();
int size_on_left = node_size(nodes_[current].left);
if (left_size <= size_on_left) {
auto [left, right] = split(nodes_[current].left, left_size);
nodes_[right_part].left = right;
nodes_[right_part].right = nodes_[current].right;
nodes_[current].left = left;
nodes_[current].right = -1;
} else {
auto [left, right] =
split(nodes_[current].right, left_size - size_on_left);
nodes_[current].right = left;
nodes_[right_part].right = right;
}
pull(current);
pull(right_part);
return {current, right_part};
}
void split_at(int position) {
if (position == size_ || block_starts_.contains(position)) {
return;
}
int start = block_starts_.prev(position);
int finish = block_starts_.next(start + 1);
assert(start >= 0 && finish > position);
block_starts_.insert(position);
if (!reversed_[start]) {
auto [left, right] = split(roots_[start], position - start);
roots_[start] = left;
roots_[position] = right;
reversed_[start] = reversed_[position] = false;
block_products_.set(start, forward_product(left));
block_products_.set(position, forward_product(right));
} else {
auto [low_keys, high_keys] = split(roots_[start], finish - position);
roots_[start] = high_keys;
roots_[position] = low_keys;
reversed_[start] = reversed_[position] = true;
block_products_.set(start, backward_product(high_keys));
block_products_.set(position, backward_product(low_keys));
}
}
void make_boundary(int position) {
maybe_rebuild();
split_at(position);
}
void maybe_rebuild() {
if (nodes_.size() * 10 > rebuild_limit_ * 9) {
rebuild();
}
}
void materialize(int current, int low, int high, bool reversed,
std::vector<int> &keys,
std::vector<value_type> &values) const {
if (current == -1) {
return;
}
if (low + 1 == high) {
keys.push_back(low);
values.push_back(nodes_[current].forward);
return;
}
int middle = (low + high) / 2;
if (!reversed) {
materialize(nodes_[current].left, low, middle, false, keys, values);
materialize(nodes_[current].right, middle, high, false, keys, values);
} else {
materialize(nodes_[current].right, middle, high, true, keys, values);
materialize(nodes_[current].left, low, middle, true, keys, values);
}
}
void rebuild() {
std::vector<int> keys;
std::vector<value_type> values;
keys.reserve(size_);
values.reserve(size_);
for (int start = block_starts_.next(0); start < size_;
start = block_starts_.next(start + 1)) {
materialize(roots_[start], 0, key_count_, reversed_[start], keys,
values);
}
assert(int(keys.size()) == size_);
initialize(keys, values);
}
void initialize(const std::vector<int> &keys,
const std::vector<value_type> &values) {
nodes_.clear();
block_starts_ = fast_set(size_);
block_products_ = segtree<Monoid>(values);
reversed_.assign(size_, false);
roots_.assign(size_, -1);
for (int position = 0; position < size_; position++) {
assert(0 <= keys[position] && keys[position] < key_count_);
block_starts_.insert(position);
roots_[position] = make_node();
set_key(roots_[position], 0, key_count_, keys[position],
values[position]);
}
}
};
} // namespace noya
#endif // NOYA_SORTABLE_SEGMENT_TREE_HPP
#include <algorithm>
#include <assert.h>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
/// @complexity Time: O(n log K) construction; a sequence of q point updates,
/// range products, and range sorts takes O((n + q)(log n + log K)) amortized,
/// where keys lie in [0, K). Space: O(n log K).
/// @complexity Time: O(log_64 n) predecessor/successor operations.
/// Space: O(n / 64).
namespace noya {
/// @brief Fixed-universe ordered set implemented as a hierarchy of bitsets.
/// Level zero marks present keys and every higher level marks nonempty words
/// below it. A predecessor or successor first scans one machine word, climbs
/// until it finds a nonempty sibling, then descends through extreme set bits.
struct fast_set {
// max{ceil(log_64(n)), 1}
int log64N, n;
std::vector<unsigned long long> a[6];
explicit fast_set(int n_ = 0) : n(n_) {
assert(n >= 0);
int m = n ? n : 1;
for (int d = 0;; ++d) {
m = (m + 63) >> 6;
a[d].assign(m, 0);
if (m == 1) {
log64N = d + 1;
break;
}
}
}
bool empty() const { return !a[log64N - 1][0]; }
bool contains(int x) const { return (a[0][x >> 6] >> (x & 63)) & 1; }
void insert(int x) {
for (int d = 0; d < log64N; ++d) {
const int q = x >> 6, r = x & 63;
a[d][q] |= 1ULL << r;
x = q;
}
}
void erase(int x) {
for (int d = 0; d < log64N; ++d) {
const int q = x >> 6, r = x & 63;
if ((a[d][q] &= ~(1ULL << r)))
break;
x = q;
}
}
/// @brief Find max element <= x, or -1 if none.
int prev(int x) const {
if (x > n - 1)
x = n - 1;
for (int d = 0; d <= log64N; ++d) {
if (x < 0)
break;
const int q = x >> 6, r = x & 63;
const unsigned long long lower = a[d][q] << (63 - r);
if (lower) {
x -= __builtin_clzll(lower);
for (int e = d; --e >= 0;)
x = x << 6 | (63 - __builtin_clzll(a[e][x]));
return x;
}
x = q - 1;
}
return -1;
}
/// @brief Find min element >= x, or n if none.
int next(int x) const {
if (x < 0)
x = 0;
for (int d = 0; d < log64N; ++d) {
const int q = x >> 6, r = x & 63;
if (static_cast<unsigned>(q) >= a[d].size())
break;
const unsigned long long upper = a[d][q] >> r;
if (upper) {
x += __builtin_ctzll(upper);
for (int e = d; --e >= 0;)
x = x << 6 | __builtin_ctzll(a[e][x]);
return x;
}
x = q + 1;
}
return n;
}
};
template <class T> struct painter {
int n;
fast_set s;
std::vector<T> ts;
painter() {}
painter(int n_, const T &t) : n(n_), s(n + 1), ts(n + 2, t) {}
template <class F> void paint(int a, int b, const T &t, F f) {
assert(0 <= a);
assert(a <= b);
assert(b <= n);
if (a == b)
return;
// auto it = this->lower_bound(a);
int c = s.next(a);
if (b < c) {
f(a, b, ts[c]);
s.insert(a);
ts[a] = ts[c];
s.insert(b);
ts[b] = t;
} else if (a < c) {
const T ta = ts[c];
int k = a;
for (; c <= b; s.erase(c), c = s.next(c)) {
f(k, c, ts[c]);
k = c;
}
if (k < b) {
f(k, b, ts[c]);
}
s.insert(a);
ts[a] = ta;
s.insert(b);
ts[b] = t;
} else {
c = s.next(c + 1);
int k = a;
for (; c <= b; s.erase(c), c = s.next(c)) {
f(k, c, ts[c]);
k = c;
}
if (k < b) {
f(k, b, ts[c]);
}
s.insert(b);
ts[b] = t;
}
}
void paint(int a, int b, const T &t) {
paint(a, b, t, [&](int, int, const T &) -> void {});
}
T get(int k) const {
assert(0 <= k);
assert(k < n);
return ts[s.next(k + 1)];
}
};
} // namespace noya
/// @complexity Time: O(n) build and O(log n) point update/range product.
/// Space: O(n).
namespace noya {
/// @brief Segment tree for a monoid type.
/// Monoid must provide `using value_type`, `value_type unit()`, and
/// `value_type op(value_type, value_type)`.
template <class Monoid> struct segtree {
using MX = Monoid;
using S = typename MX::value_type;
using value_type = S;
int n = 0;
int size = 1;
std::vector<S> d;
segtree() {}
explicit segtree(int _n) { build(_n); }
explicit segtree(const std::vector<S> &v) { build(v); }
template <class F> segtree(int _n, F f) { build(_n, f); }
void build(int _n) { build(_n, [](int) { return MX::unit(); }); }
void build(const std::vector<S> &v) {
build(int(v.size()), [&](int i) { return v[i]; });
}
template <class F> void build(int _n, F f) {
n = _n;
size = 1;
while (size < n)
size <<= 1;
d.assign(size << 1, MX::unit());
for (int i = 0; i < n; i++)
d[size + i] = f(i);
for (int i = size - 1; i >= 1; i--)
update(i);
}
void set(int p, S x) {
assert(0 <= p && p < n);
p += size;
d[p] = x;
while (p >>= 1)
update(p);
}
void multiply(int p, S x) {
assert(0 <= p && p < n);
p += size;
d[p] = MX::op(d[p], x);
while (p >>= 1)
update(p);
}
S get(int p) const {
assert(0 <= p && p < n);
return d[p + size];
}
std::vector<S> get_all() const {
return std::vector<S>(d.begin() + size, d.begin() + size + n);
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
S sml = MX::unit(), smr = MX::unit();
l += size;
r += size;
while (l < r) {
if (l & 1)
sml = MX::op(sml, d[l++]);
if (r & 1)
smr = MX::op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return MX::op(sml, smr);
}
S all_prod() const { return d[1]; }
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= n);
assert(f(MX::unit()));
if (l == n)
return n;
l += size;
S sm = MX::unit();
do {
while ((l & 1) == 0)
l >>= 1;
if (!f(MX::op(sm, d[l]))) {
while (l < size) {
l <<= 1;
if (f(MX::op(sm, d[l]))) {
sm = MX::op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = MX::op(sm, d[l++]);
} while ((l & -l) != l);
return n;
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= n);
assert(f(MX::unit()));
if (r == 0)
return 0;
r += size;
S sm = MX::unit();
do {
--r;
while (r > 1 && (r & 1))
r >>= 1;
if (!f(MX::op(d[r], sm))) {
while (r < size) {
r = (r << 1) | 1;
if (f(MX::op(d[r], sm))) {
sm = MX::op(d[r], sm);
--r;
}
}
return r + 1 - size;
}
sm = MX::op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
void update(int k) { d[k] = MX::op(d[k << 1], d[k << 1 | 1]); }
};
} // namespace noya
namespace noya {
/// @brief Maintain a sequence of distinct integer keys and monoid values under
/// point replacement, ordered range product, and sorting a range by key. Each
/// maximal already-sorted block is stored as a sparse segment tree over key
/// space, containing both forward and backward products. Sorting joins all
/// blocks in the range; splitting a block by sequence rank restores query
/// boundaries. A fast set tracks block starts and an outer segment tree stores
/// one aggregate per block. Since an operation creates only O(1) boundaries,
/// the total number of block splits and merges is linear in the operation
/// count; periodic rebuilding bounds the persistent split-node storage.
template <class Monoid> class sortable_segment_tree {
public:
using value_type = typename Monoid::value_type;
private:
struct node {
value_type forward;
value_type backward;
int size = 1;
int left = -1;
int right = -1;
};
int size_ = 0;
int key_count_ = 0;
int key_log_ = 0;
std::size_t rebuild_limit_ = 0;
fast_set block_starts_;
segtree<Monoid> block_products_;
std::vector<bool> reversed_;
std::vector<int> roots_;
std::vector<node> nodes_;
public:
sortable_segment_tree() = default;
sortable_segment_tree(int key_count, const std::vector<int> &keys,
const std::vector<value_type> &values) {
build(key_count, keys, values);
}
void build(int key_count, const std::vector<int> &keys,
const std::vector<value_type> &values) {
assert(!keys.empty());
assert(keys.size() == values.size());
assert(key_count > 0);
size_ = int(keys.size());
key_count_ = key_count;
key_log_ = 0;
for (int range = 1; range < key_count_;) {
range <<= 1;
key_log_++;
}
rebuild_limit_ = std::max<std::size_t>(
4096, std::size_t(size_) * std::size_t(key_log_ + 1) * 2 + 1024);
initialize(keys, values);
}
int size() const { return size_; }
void set(int position, int key, const value_type &value) {
assert(0 <= position && position < size_);
assert(0 <= key && key < key_count_);
make_boundary(position);
make_boundary(position + 1);
maybe_rebuild();
reversed_[position] = false;
roots_[position] = make_node();
set_key(roots_[position], 0, key_count_, key, value);
block_products_.set(position, value);
}
value_type prod(int left, int right) {
assert(0 <= left && left <= right && right <= size_);
if (left == right) {
return Monoid::unit();
}
make_boundary(left);
make_boundary(right);
return block_products_.prod(left, right);
}
value_type all_prod() const { return block_products_.all_prod(); }
void sort_ascending(int left, int right) {
assert(0 <= left && left <= right && right <= size_);
if (left == right) {
return;
}
make_boundary(left);
make_boundary(right);
while (true) {
maybe_rebuild();
int next_start = block_starts_.next(left + 1);
if (next_start == right) {
break;
}
roots_[left] = merge(roots_[left], roots_[next_start]);
block_starts_.erase(next_start);
block_products_.set(next_start, Monoid::unit());
}
reversed_[left] = false;
block_products_.set(left, forward_product(roots_[left]));
}
void sort_descending(int left, int right) {
assert(0 <= left && left <= right && right <= size_);
if (left == right) {
return;
}
sort_ascending(left, right);
reversed_[left] = true;
block_products_.set(left, backward_product(roots_[left]));
}
private:
int node_size(int current) const {
return current == -1 ? 0 : nodes_[current].size;
}
value_type forward_product(int current) const {
return current == -1 ? Monoid::unit() : nodes_[current].forward;
}
value_type backward_product(int current) const {
return current == -1 ? Monoid::unit() : nodes_[current].backward;
}
int make_node(value_type value = Monoid::unit()) {
nodes_.push_back({value, value, 1, -1, -1});
return int(nodes_.size()) - 1;
}
void pull(int current) {
int left = nodes_[current].left;
int right = nodes_[current].right;
if (left == -1 && right == -1) {
return;
}
nodes_[current].size = node_size(left) + node_size(right);
nodes_[current].forward =
Monoid::op(forward_product(left), forward_product(right));
nodes_[current].backward =
Monoid::op(backward_product(right), backward_product(left));
}
void set_key(int current, int low, int high, int key,
const value_type &value) {
if (low + 1 == high) {
nodes_[current].forward = nodes_[current].backward = value;
return;
}
int middle = (low + high) / 2;
if (key < middle) {
if (nodes_[current].left == -1) {
nodes_[current].left = make_node();
}
set_key(nodes_[current].left, low, middle, key, value);
} else {
if (nodes_[current].right == -1) {
nodes_[current].right = make_node();
}
set_key(nodes_[current].right, middle, high, key, value);
}
pull(current);
}
int merge(int first, int second) {
if (first == -1 || second == -1) {
return first == -1 ? second : first;
}
nodes_[first].left = merge(nodes_[first].left, nodes_[second].left);
nodes_[first].right = merge(nodes_[first].right, nodes_[second].right);
pull(first);
return first;
}
std::pair<int, int> split(int current, int left_size) {
assert(current != -1);
assert(0 <= left_size && left_size <= nodes_[current].size);
if (left_size == 0) {
return {-1, current};
}
if (left_size == nodes_[current].size) {
return {current, -1};
}
int right_part = make_node();
int size_on_left = node_size(nodes_[current].left);
if (left_size <= size_on_left) {
auto [left, right] = split(nodes_[current].left, left_size);
nodes_[right_part].left = right;
nodes_[right_part].right = nodes_[current].right;
nodes_[current].left = left;
nodes_[current].right = -1;
} else {
auto [left, right] =
split(nodes_[current].right, left_size - size_on_left);
nodes_[current].right = left;
nodes_[right_part].right = right;
}
pull(current);
pull(right_part);
return {current, right_part};
}
void split_at(int position) {
if (position == size_ || block_starts_.contains(position)) {
return;
}
int start = block_starts_.prev(position);
int finish = block_starts_.next(start + 1);
assert(start >= 0 && finish > position);
block_starts_.insert(position);
if (!reversed_[start]) {
auto [left, right] = split(roots_[start], position - start);
roots_[start] = left;
roots_[position] = right;
reversed_[start] = reversed_[position] = false;
block_products_.set(start, forward_product(left));
block_products_.set(position, forward_product(right));
} else {
auto [low_keys, high_keys] = split(roots_[start], finish - position);
roots_[start] = high_keys;
roots_[position] = low_keys;
reversed_[start] = reversed_[position] = true;
block_products_.set(start, backward_product(high_keys));
block_products_.set(position, backward_product(low_keys));
}
}
void make_boundary(int position) {
maybe_rebuild();
split_at(position);
}
void maybe_rebuild() {
if (nodes_.size() * 10 > rebuild_limit_ * 9) {
rebuild();
}
}
void materialize(int current, int low, int high, bool reversed,
std::vector<int> &keys,
std::vector<value_type> &values) const {
if (current == -1) {
return;
}
if (low + 1 == high) {
keys.push_back(low);
values.push_back(nodes_[current].forward);
return;
}
int middle = (low + high) / 2;
if (!reversed) {
materialize(nodes_[current].left, low, middle, false, keys, values);
materialize(nodes_[current].right, middle, high, false, keys, values);
} else {
materialize(nodes_[current].right, middle, high, true, keys, values);
materialize(nodes_[current].left, low, middle, true, keys, values);
}
}
void rebuild() {
std::vector<int> keys;
std::vector<value_type> values;
keys.reserve(size_);
values.reserve(size_);
for (int start = block_starts_.next(0); start < size_;
start = block_starts_.next(start + 1)) {
materialize(roots_[start], 0, key_count_, reversed_[start], keys,
values);
}
assert(int(keys.size()) == size_);
initialize(keys, values);
}
void initialize(const std::vector<int> &keys,
const std::vector<value_type> &values) {
nodes_.clear();
block_starts_ = fast_set(size_);
block_products_ = segtree<Monoid>(values);
reversed_.assign(size_, false);
roots_.assign(size_, -1);
for (int position = 0; position < size_; position++) {
assert(0 <= keys[position] && keys[position] < key_count_);
block_starts_.insert(position);
roots_[position] = make_node();
set_key(roots_[position], 0, key_count_, keys[position],
values[position]);
}
}
};
} // namespace noya