sortable_segment_tree.hpp¶
维护序列的单点修改、区间升降序排序和区间复合查询；适合排序后仍需按顺序聚合函数或矩阵的题目。
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).
AC 记录：point_set_range_sort_range_composite。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 fwd;
value_type bwd;
int sz = 1;
int ls = -1;
int rs = -1;
};
int n = 0;
int m0 = 0;
int lg = 0;
std::size_t lim = 0;
fast_set ss;
segtree<Monoid> seg;
std::vector<bool> rev;
std::vector<int> rt;
std::vector<node> tr;
public:
sortable_segment_tree() = default;
sortable_segment_tree(int m, const std::vector<int> &k,
const std::vector<value_type> &a) {
build(m, k, a);
}
void build(int m, const std::vector<int> &k,
const std::vector<value_type> &a) {
assert(!k.empty());
assert(k.size() == a.size());
assert(m > 0);
n = int(k.size());
m0 = m;
lg = 0;
for (int rng = 1; rng < m0;) {
rng <<= 1;
lg++;
}
lim = std::max<std::size_t>(4096, std::size_t(n) * std::size_t(lg + 1) * 2 +
1024);
initialize(k, a);
}
int size() const { return n; }
void set(int pos, int key, const value_type &val) {
assert(0 <= pos && pos < n);
assert(0 <= key && key < m0);
make_boundary(pos);
make_boundary(pos + 1);
maybe_rebuild();
rev[pos] = false;
rt[pos] = make_node();
set_key(rt[pos], 0, m0, key, val);
seg.set(pos, val);
}
value_type prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return Monoid::unit();
}
make_boundary(l);
make_boundary(r);
return seg.prod(l, r);
}
value_type all_prod() const { return seg.all_prod(); }
void sort_ascending(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
make_boundary(l);
make_boundary(r);
while (true) {
maybe_rebuild();
int nl = ss.next(l + 1);
if (nl == r) {
break;
}
rt[l] = merge(rt[l], rt[nl]);
ss.erase(nl);
seg.set(nl, Monoid::unit());
}
rev[l] = false;
seg.set(l, forward_product(rt[l]));
}
void sort_descending(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
sort_ascending(l, r);
rev[l] = true;
seg.set(l, backward_product(rt[l]));
}
private:
int node_size(int cur) const { return cur == -1 ? 0 : tr[cur].sz; }
value_type forward_product(int cur) const {
return cur == -1 ? Monoid::unit() : tr[cur].fwd;
}
value_type backward_product(int cur) const {
return cur == -1 ? Monoid::unit() : tr[cur].bwd;
}
int make_node(value_type val = Monoid::unit()) {
tr.push_back({val, val, 1, -1, -1});
return int(tr.size()) - 1;
}
void pull(int cur) {
int l = tr[cur].ls;
int r = tr[cur].rs;
if (l == -1 && r == -1) {
return;
}
tr[cur].sz = node_size(l) + node_size(r);
tr[cur].fwd = Monoid::op(forward_product(l), forward_product(r));
tr[cur].bwd = Monoid::op(backward_product(r), backward_product(l));
}
void set_key(int cur, int low, int hi, int key, const value_type &val) {
if (low + 1 == hi) {
tr[cur].fwd = tr[cur].bwd = val;
return;
}
int mid = (low + hi) / 2;
if (key < mid) {
if (tr[cur].ls == -1) {
tr[cur].ls = make_node();
}
set_key(tr[cur].ls, low, mid, key, val);
} else {
if (tr[cur].rs == -1) {
tr[cur].rs = make_node();
}
set_key(tr[cur].rs, mid, hi, key, val);
}
pull(cur);
}
int merge(int arr, int b) {
if (arr == -1 || b == -1) {
return arr == -1 ? b : arr;
}
tr[arr].ls = merge(tr[arr].ls, tr[b].ls);
tr[arr].rs = merge(tr[arr].rs, tr[b].rs);
pull(arr);
return arr;
}
std::pair<int, int> split(int cur, int lsz) {
assert(cur != -1);
assert(0 <= lsz && lsz <= tr[cur].sz);
if (lsz == 0) {
return {-1, cur};
}
if (lsz == tr[cur].sz) {
return {cur, -1};
}
int rp = make_node();
int cl = node_size(tr[cur].ls);
if (lsz <= cl) {
auto [l, r] = split(tr[cur].ls, lsz);
tr[rp].ls = r;
tr[rp].rs = tr[cur].rs;
tr[cur].ls = l;
tr[cur].rs = -1;
} else {
auto [l, r] = split(tr[cur].rs, lsz - cl);
tr[cur].rs = l;
tr[rp].rs = r;
}
pull(cur);
pull(rp);
return {cur, rp};
}
void split_at(int pos) {
if (pos == n || ss.contains(pos)) {
return;
}
int st = ss.prev(pos);
int ed = ss.next(st + 1);
assert(st >= 0 && ed > pos);
ss.insert(pos);
if (!rev[st]) {
auto [l, r] = split(rt[st], pos - st);
rt[st] = l;
rt[pos] = r;
rev[st] = rev[pos] = false;
seg.set(st, forward_product(l));
seg.set(pos, forward_product(r));
} else {
auto [kl, kh] = split(rt[st], ed - pos);
rt[st] = kh;
rt[pos] = kl;
rev[st] = rev[pos] = true;
seg.set(st, backward_product(kh));
seg.set(pos, backward_product(kl));
}
}
void make_boundary(int pos) {
maybe_rebuild();
split_at(pos);
}
void maybe_rebuild() {
if (tr.size() * 10 > lim * 9) {
rebuild();
}
}
void materialize(int cur, int low, int hi, bool re0, std::vector<int> &k,
std::vector<value_type> &a) const {
if (cur == -1) {
return;
}
if (low + 1 == hi) {
k.push_back(low);
a.push_back(tr[cur].fwd);
return;
}
int mid = (low + hi) / 2;
if (!re0) {
materialize(tr[cur].ls, low, mid, false, k, a);
materialize(tr[cur].rs, mid, hi, false, k, a);
} else {
materialize(tr[cur].rs, mid, hi, true, k, a);
materialize(tr[cur].ls, low, mid, true, k, a);
}
}
void rebuild() {
std::vector<int> k;
std::vector<value_type> a;
k.reserve(n);
a.reserve(n);
for (int st = ss.next(0); st < n; st = ss.next(st + 1)) {
materialize(rt[st], 0, m0, rev[st], k, a);
}
assert(int(k.size()) == n);
initialize(k, a);
}
void initialize(const std::vector<int> &k, const std::vector<value_type> &a) {
tr.clear();
ss = fast_set(n);
seg = segtree<Monoid>(a);
rev.assign(n, false);
rt.assign(n, -1);
for (int pos = 0; pos < n; pos++) {
assert(0 <= k[pos] && k[pos] < m0);
ss.insert(pos);
rt[pos] = make_node();
set_key(rt[pos], 0, m0, k[pos], a[pos]);
}
}
};
} // namespace noya
#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 fwd;
value_type bwd;
int sz = 1;
int ls = -1;
int rs = -1;
};
int n = 0;
int m0 = 0;
int lg = 0;
std::size_t lim = 0;
fast_set ss;
segtree<Monoid> seg;
std::vector<bool> rev;
std::vector<int> rt;
std::vector<node> tr;
public:
sortable_segment_tree() = default;
sortable_segment_tree(int m, const std::vector<int> &k,
const std::vector<value_type> &a) {
build(m, k, a);
}
void build(int m, const std::vector<int> &k,
const std::vector<value_type> &a) {
assert(!k.empty());
assert(k.size() == a.size());
assert(m > 0);
n = int(k.size());
m0 = m;
lg = 0;
for (int rng = 1; rng < m0;) {
rng <<= 1;
lg++;
}
lim = std::max<std::size_t>(4096, std::size_t(n) * std::size_t(lg + 1) * 2 +
1024);
initialize(k, a);
}
int size() const { return n; }
void set(int pos, int key, const value_type &val) {
assert(0 <= pos && pos < n);
assert(0 <= key && key < m0);
make_boundary(pos);
make_boundary(pos + 1);
maybe_rebuild();
rev[pos] = false;
rt[pos] = make_node();
set_key(rt[pos], 0, m0, key, val);
seg.set(pos, val);
}
value_type prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return Monoid::unit();
}
make_boundary(l);
make_boundary(r);
return seg.prod(l, r);
}
value_type all_prod() const { return seg.all_prod(); }
void sort_ascending(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
make_boundary(l);
make_boundary(r);
while (true) {
maybe_rebuild();
int nl = ss.next(l + 1);
if (nl == r) {
break;
}
rt[l] = merge(rt[l], rt[nl]);
ss.erase(nl);
seg.set(nl, Monoid::unit());
}
rev[l] = false;
seg.set(l, forward_product(rt[l]));
}
void sort_descending(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
sort_ascending(l, r);
rev[l] = true;
seg.set(l, backward_product(rt[l]));
}
private:
int node_size(int cur) const { return cur == -1 ? 0 : tr[cur].sz; }
value_type forward_product(int cur) const {
return cur == -1 ? Monoid::unit() : tr[cur].fwd;
}
value_type backward_product(int cur) const {
return cur == -1 ? Monoid::unit() : tr[cur].bwd;
}
int make_node(value_type val = Monoid::unit()) {
tr.push_back({val, val, 1, -1, -1});
return int(tr.size()) - 1;
}
void pull(int cur) {
int l = tr[cur].ls;
int r = tr[cur].rs;
if (l == -1 && r == -1) {
return;
}
tr[cur].sz = node_size(l) + node_size(r);
tr[cur].fwd = Monoid::op(forward_product(l), forward_product(r));
tr[cur].bwd = Monoid::op(backward_product(r), backward_product(l));
}
void set_key(int cur, int low, int hi, int key, const value_type &val) {
if (low + 1 == hi) {
tr[cur].fwd = tr[cur].bwd = val;
return;
}
int mid = (low + hi) / 2;
if (key < mid) {
if (tr[cur].ls == -1) {
tr[cur].ls = make_node();
}
set_key(tr[cur].ls, low, mid, key, val);
} else {
if (tr[cur].rs == -1) {
tr[cur].rs = make_node();
}
set_key(tr[cur].rs, mid, hi, key, val);
}
pull(cur);
}
int merge(int arr, int b) {
if (arr == -1 || b == -1) {
return arr == -1 ? b : arr;
}
tr[arr].ls = merge(tr[arr].ls, tr[b].ls);
tr[arr].rs = merge(tr[arr].rs, tr[b].rs);
pull(arr);
return arr;
}
std::pair<int, int> split(int cur, int lsz) {
assert(cur != -1);
assert(0 <= lsz && lsz <= tr[cur].sz);
if (lsz == 0) {
return {-1, cur};
}
if (lsz == tr[cur].sz) {
return {cur, -1};
}
int rp = make_node();
int cl = node_size(tr[cur].ls);
if (lsz <= cl) {
auto [l, r] = split(tr[cur].ls, lsz);
tr[rp].ls = r;
tr[rp].rs = tr[cur].rs;
tr[cur].ls = l;
tr[cur].rs = -1;
} else {
auto [l, r] = split(tr[cur].rs, lsz - cl);
tr[cur].rs = l;
tr[rp].rs = r;
}
pull(cur);
pull(rp);
return {cur, rp};
}
void split_at(int pos) {
if (pos == n || ss.contains(pos)) {
return;
}
int st = ss.prev(pos);
int ed = ss.next(st + 1);
assert(st >= 0 && ed > pos);
ss.insert(pos);
if (!rev[st]) {
auto [l, r] = split(rt[st], pos - st);
rt[st] = l;
rt[pos] = r;
rev[st] = rev[pos] = false;
seg.set(st, forward_product(l));
seg.set(pos, forward_product(r));
} else {
auto [kl, kh] = split(rt[st], ed - pos);
rt[st] = kh;
rt[pos] = kl;
rev[st] = rev[pos] = true;
seg.set(st, backward_product(kh));
seg.set(pos, backward_product(kl));
}
}
void make_boundary(int pos) {
maybe_rebuild();
split_at(pos);
}
void maybe_rebuild() {
if (tr.size() * 10 > lim * 9) {
rebuild();
}
}
void materialize(int cur, int low, int hi, bool re0, std::vector<int> &k,
std::vector<value_type> &a) const {
if (cur == -1) {
return;
}
if (low + 1 == hi) {
k.push_back(low);
a.push_back(tr[cur].fwd);
return;
}
int mid = (low + hi) / 2;
if (!re0) {
materialize(tr[cur].ls, low, mid, false, k, a);
materialize(tr[cur].rs, mid, hi, false, k, a);
} else {
materialize(tr[cur].rs, mid, hi, true, k, a);
materialize(tr[cur].ls, low, mid, true, k, a);
}
}
void rebuild() {
std::vector<int> k;
std::vector<value_type> a;
k.reserve(n);
a.reserve(n);
for (int st = ss.next(0); st < n; st = ss.next(st + 1)) {
materialize(rt[st], 0, m0, rev[st], k, a);
}
assert(int(k.size()) == n);
initialize(k, a);
}
void initialize(const std::vector<int> &k, const std::vector<value_type> &a) {
tr.clear();
ss = fast_set(n);
seg = segtree<Monoid>(a);
rev.assign(n, false);
rt.assign(n, -1);
for (int pos = 0; pos < n; pos++) {
assert(0 <= k[pos] && k[pos] < m0);
ss.insert(pos);
rt[pos] = make_node();
set_key(rt[pos], 0, m0, k[pos], a[pos]);
}
}
};
} // 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 lg, 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) {
lg = d + 1;
break;
}
}
}
bool empty() const { return !a[lg - 1][0]; }
bool contains(int x) const { return (a[0][x >> 6] >> (x & 63)) & 1; }
void insert(int x) {
for (int d = 0; d < lg; ++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 < lg; ++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 <= lg; ++d) {
if (x < 0)
break;
const int q = x >> 6, r = x & 63;
const unsigned long long lo = a[d][q] << (63 - r);
if (lo) {
x -= __builtin_clzll(lo);
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 < lg; ++d) {
const int q = x >> 6, r = x & 63;
if (static_cast<unsigned>(q) >= a[d].size())
break;
const unsigned long long hi = a[d][q] >> r;
if (hi) {
x += __builtin_ctzll(hi);
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 sz = 1;
std::vector<S> d;
segtree() : segtree(0) {}
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;
sz = 1;
while (sz < n)
sz <<= 1;
d.assign(sz << 1, MX::unit());
for (int i = 0; i < n; i++)
d[sz + i] = f(i);
for (int i = sz - 1; i >= 1; i--)
update(i);
}
void set(int p, S x) {
assert(0 <= p && p < n);
p += sz;
d[p] = x;
while (p >>= 1)
update(p);
}
void multiply(int p, S x) {
assert(0 <= p && p < n);
p += sz;
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 + sz];
}
std::vector<S> get_all() const {
return std::vector<S>(d.begin() + sz, d.begin() + sz + n);
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
S sml = MX::unit(), smr = MX::unit();
l += sz;
r += sz;
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 += sz;
S sm = MX::unit();
do {
while ((l & 1) == 0)
l >>= 1;
if (!f(MX::op(sm, d[l]))) {
while (l < sz) {
l <<= 1;
if (f(MX::op(sm, d[l]))) {
sm = MX::op(sm, d[l]);
l++;
}
}
return l - sz;
}
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 += sz;
S sm = MX::unit();
do {
--r;
while (r > 1 && (r & 1))
r >>= 1;
if (!f(MX::op(d[r], sm))) {
while (r < sz) {
r = (r << 1) | 1;
if (f(MX::op(d[r], sm))) {
sm = MX::op(d[r], sm);
--r;
}
}
return r + 1 - sz;
}
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 fwd;
value_type bwd;
int sz = 1;
int ls = -1;
int rs = -1;
};
int n = 0;
int m0 = 0;
int lg = 0;
std::size_t lim = 0;
fast_set ss;
segtree<Monoid> seg;
std::vector<bool> rev;
std::vector<int> rt;
std::vector<node> tr;
public:
sortable_segment_tree() = default;
sortable_segment_tree(int m, const std::vector<int> &k,
const std::vector<value_type> &a) {
build(m, k, a);
}
void build(int m, const std::vector<int> &k,
const std::vector<value_type> &a) {
assert(!k.empty());
assert(k.size() == a.size());
assert(m > 0);
n = int(k.size());
m0 = m;
lg = 0;
for (int rng = 1; rng < m0;) {
rng <<= 1;
lg++;
}
lim = std::max<std::size_t>(4096, std::size_t(n) * std::size_t(lg + 1) * 2 +
1024);
initialize(k, a);
}
int size() const { return n; }
void set(int pos, int key, const value_type &val) {
assert(0 <= pos && pos < n);
assert(0 <= key && key < m0);
make_boundary(pos);
make_boundary(pos + 1);
maybe_rebuild();
rev[pos] = false;
rt[pos] = make_node();
set_key(rt[pos], 0, m0, key, val);
seg.set(pos, val);
}
value_type prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return Monoid::unit();
}
make_boundary(l);
make_boundary(r);
return seg.prod(l, r);
}
value_type all_prod() const { return seg.all_prod(); }
void sort_ascending(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
make_boundary(l);
make_boundary(r);
while (true) {
maybe_rebuild();
int nl = ss.next(l + 1);
if (nl == r) {
break;
}
rt[l] = merge(rt[l], rt[nl]);
ss.erase(nl);
seg.set(nl, Monoid::unit());
}
rev[l] = false;
seg.set(l, forward_product(rt[l]));
}
void sort_descending(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
sort_ascending(l, r);
rev[l] = true;
seg.set(l, backward_product(rt[l]));
}
private:
int node_size(int cur) const { return cur == -1 ? 0 : tr[cur].sz; }
value_type forward_product(int cur) const {
return cur == -1 ? Monoid::unit() : tr[cur].fwd;
}
value_type backward_product(int cur) const {
return cur == -1 ? Monoid::unit() : tr[cur].bwd;
}
int make_node(value_type val = Monoid::unit()) {
tr.push_back({val, val, 1, -1, -1});
return int(tr.size()) - 1;
}
void pull(int cur) {
int l = tr[cur].ls;
int r = tr[cur].rs;
if (l == -1 && r == -1) {
return;
}
tr[cur].sz = node_size(l) + node_size(r);
tr[cur].fwd = Monoid::op(forward_product(l), forward_product(r));
tr[cur].bwd = Monoid::op(backward_product(r), backward_product(l));
}
void set_key(int cur, int low, int hi, int key, const value_type &val) {
if (low + 1 == hi) {
tr[cur].fwd = tr[cur].bwd = val;
return;
}
int mid = (low + hi) / 2;
if (key < mid) {
if (tr[cur].ls == -1) {
tr[cur].ls = make_node();
}
set_key(tr[cur].ls, low, mid, key, val);
} else {
if (tr[cur].rs == -1) {
tr[cur].rs = make_node();
}
set_key(tr[cur].rs, mid, hi, key, val);
}
pull(cur);
}
int merge(int arr, int b) {
if (arr == -1 || b == -1) {
return arr == -1 ? b : arr;
}
tr[arr].ls = merge(tr[arr].ls, tr[b].ls);
tr[arr].rs = merge(tr[arr].rs, tr[b].rs);
pull(arr);
return arr;
}
std::pair<int, int> split(int cur, int lsz) {
assert(cur != -1);
assert(0 <= lsz && lsz <= tr[cur].sz);
if (lsz == 0) {
return {-1, cur};
}
if (lsz == tr[cur].sz) {
return {cur, -1};
}
int rp = make_node();
int cl = node_size(tr[cur].ls);
if (lsz <= cl) {
auto [l, r] = split(tr[cur].ls, lsz);
tr[rp].ls = r;
tr[rp].rs = tr[cur].rs;
tr[cur].ls = l;
tr[cur].rs = -1;
} else {
auto [l, r] = split(tr[cur].rs, lsz - cl);
tr[cur].rs = l;
tr[rp].rs = r;
}
pull(cur);
pull(rp);
return {cur, rp};
}
void split_at(int pos) {
if (pos == n || ss.contains(pos)) {
return;
}
int st = ss.prev(pos);
int ed = ss.next(st + 1);
assert(st >= 0 && ed > pos);
ss.insert(pos);
if (!rev[st]) {
auto [l, r] = split(rt[st], pos - st);
rt[st] = l;
rt[pos] = r;
rev[st] = rev[pos] = false;
seg.set(st, forward_product(l));
seg.set(pos, forward_product(r));
} else {
auto [kl, kh] = split(rt[st], ed - pos);
rt[st] = kh;
rt[pos] = kl;
rev[st] = rev[pos] = true;
seg.set(st, backward_product(kh));
seg.set(pos, backward_product(kl));
}
}
void make_boundary(int pos) {
maybe_rebuild();
split_at(pos);
}
void maybe_rebuild() {
if (tr.size() * 10 > lim * 9) {
rebuild();
}
}
void materialize(int cur, int low, int hi, bool re0, std::vector<int> &k,
std::vector<value_type> &a) const {
if (cur == -1) {
return;
}
if (low + 1 == hi) {
k.push_back(low);
a.push_back(tr[cur].fwd);
return;
}
int mid = (low + hi) / 2;
if (!re0) {
materialize(tr[cur].ls, low, mid, false, k, a);
materialize(tr[cur].rs, mid, hi, false, k, a);
} else {
materialize(tr[cur].rs, mid, hi, true, k, a);
materialize(tr[cur].ls, low, mid, true, k, a);
}
}
void rebuild() {
std::vector<int> k;
std::vector<value_type> a;
k.reserve(n);
a.reserve(n);
for (int st = ss.next(0); st < n; st = ss.next(st + 1)) {
materialize(rt[st], 0, m0, rev[st], k, a);
}
assert(int(k.size()) == n);
initialize(k, a);
}
void initialize(const std::vector<int> &k, const std::vector<value_type> &a) {
tr.clear();
ss = fast_set(n);
seg = segtree<Monoid>(a);
rev.assign(n, false);
rt.assign(n, -1);
for (int pos = 0; pos < n; pos++) {
assert(0 <= k[pos] && k[pos] < m0);
ss.insert(pos);
rt[pos] = make_node();
set_key(rt[pos], 0, m0, k[pos], a[pos]);
}
}
};
} // namespace noya