implicit_treap.hpp¶
把序列下标隐式存进随机平衡树，支持按位置切分、合并、插入删除与区间聚合。
Complexity: Time: Expected O(log n) per split/merge/update/query. Space: O(n) nodes and O(log n) expected stack.
AC 记录：deque, deque_operate_all_composite, range_reverse_range_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Expected O(log n) per split/merge/update/query.
/// Space: O(n) nodes and O(log n) expected stack.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <vector>
namespace noya {
/// @brief Implicit randomized treap supporting insertion, erasure, reversal,
/// point updates, and ordered monoid products in expected O(log n) time.
template <class S, auto op, auto e> struct implicit_treap {
struct node {
S val;
S fwd;
S bwd;
std::uint64_t rnd = 0;
int ls = -1;
int rs = -1;
int sz = 1;
bool rev = false;
};
std::vector<node> tr;
int rt = -1;
implicit_treap() = default;
explicit implicit_treap(const std::vector<S> &a) {
tr.reserve(a.size());
for (const S &val : a) {
rt = merge(rt, make_node(val));
}
}
int size() const { return node_size(rt); }
bool empty() const { return rt == -1; }
/// @brief Insert value immediately before position.
void insert(int pos, const S &val) {
assert(0 <= pos && pos <= size());
auto [l, r] = split(rt, pos);
rt = merge(merge(l, make_node(val)), r);
}
/// @brief Erase and return the value at position.
S erase(int pos) {
assert(0 <= pos && pos < size());
auto [l, suf] = split(rt, pos);
auto [mid, r] = split(suf, 1);
assert(mid != -1);
S val = tr[mid].val;
rt = merge(l, r);
return val;
}
/// @brief Replace the value at position.
void set(int pos, const S &val) {
assert(0 <= pos && pos < size());
auto [l, suf] = split(rt, pos);
auto [mid, r] = split(suf, 1);
tr[mid].val = val;
pull(mid);
rt = merge(l, merge(mid, r));
}
/// @brief Return the value at position.
S get(int pos) {
assert(0 <= pos && pos < size());
int cur = rt;
while (cur != -1) {
push(cur);
int lsz = node_size(tr[cur].ls);
if (pos < lsz) {
cur = tr[cur].ls;
} else if (pos == lsz) {
return tr[cur].val;
} else {
pos -= lsz + 1;
cur = tr[cur].rs;
}
}
assert(false);
return e();
}
/// @brief Reverse the half-open range [l, r).
void reverse(int l, int r) {
check_range(l, r);
auto [pre, suf] = split(rt, l);
auto [mid, tl] = split(suf, r - l);
apply_reverse(mid);
rt = merge(pre, merge(mid, tl));
}
/// @brief Return the ordered monoid product over [l, r).
S prod(int l, int r) {
check_range(l, r);
auto [pre, suf] = split(rt, l);
auto [mid, tl] = split(suf, r - l);
S res = forward_product(mid);
rt = merge(pre, merge(mid, tl));
return res;
}
/// @brief Materialize the current sequence.
std::vector<S> to_vector() {
std::vector<S> res;
res.reserve(size());
auto dfs = [&](auto &f, int cur) -> void {
if (cur == -1) {
return;
}
push(cur);
f(f, tr[cur].ls);
res.push_back(tr[cur].val);
f(f, tr[cur].rs);
};
dfs(dfs, rt);
return res;
}
private:
std::uint64_t rng = 0x243f6a8885a308d3ULL;
int node_size(int cur) const { return cur == -1 ? 0 : tr[cur].sz; }
S forward_product(int cur) const { return cur == -1 ? e() : tr[cur].fwd; }
S backward_product(int cur) const { return cur == -1 ? e() : tr[cur].bwd; }
std::uint64_t next_priority() {
std::uint64_t val = (rng += 0x9e3779b97f4a7c15ULL);
val = (val ^ (val >> 30)) * 0xbf58476d1ce4e5b9ULL;
val = (val ^ (val >> 27)) * 0x94d049bb133111ebULL;
return val ^ (val >> 31);
}
int make_node(const S &val) {
tr.push_back({val, val, val, next_priority()});
return int(tr.size()) - 1;
}
void apply_reverse(int cur) {
if (cur == -1) {
return;
}
std::swap(tr[cur].ls, tr[cur].rs);
std::swap(tr[cur].fwd, tr[cur].bwd);
tr[cur].rev = !tr[cur].rev;
}
void push(int cur) {
if (cur != -1 && tr[cur].rev) {
apply_reverse(tr[cur].ls);
apply_reverse(tr[cur].rs);
tr[cur].rev = false;
}
}
void pull(int cur) {
tr[cur].sz = 1 + node_size(tr[cur].ls) + node_size(tr[cur].rs);
tr[cur].fwd = op(op(forward_product(tr[cur].ls), tr[cur].val),
forward_product(tr[cur].rs));
tr[cur].bwd = op(op(backward_product(tr[cur].rs), tr[cur].val),
backward_product(tr[cur].ls));
}
std::pair<int, int> split(int cur, int lsz) {
if (cur == -1) {
return {-1, -1};
}
push(cur);
if (node_size(tr[cur].ls) >= lsz) {
auto [l, r] = split(tr[cur].ls, lsz);
tr[cur].ls = r;
pull(cur);
return {l, cur};
}
auto [l, r] = split(tr[cur].rs, lsz - node_size(tr[cur].ls) - 1);
tr[cur].rs = l;
pull(cur);
return {cur, r};
}
int merge(int l, int r) {
if (l == -1 || r == -1) {
return l == -1 ? r : l;
}
if (tr[l].rnd > tr[r].rnd) {
push(l);
tr[l].rs = merge(tr[l].rs, r);
pull(l);
return l;
}
push(r);
tr[r].ls = merge(l, tr[r].ls);
pull(r);
return r;
}
void check_range(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
}
};
} // namespace noya
#ifndef NOYA_IMPLICIT_TREAP_HPP
#define NOYA_IMPLICIT_TREAP_HPP 1
/// @complexity Time: Expected O(log n) per split/merge/update/query.
/// Space: O(n) nodes and O(log n) expected stack.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <vector>
namespace noya {
/// @brief Implicit randomized treap supporting insertion, erasure, reversal,
/// point updates, and ordered monoid products in expected O(log n) time.
template <class S, auto op, auto e> struct implicit_treap {
struct node {
S val;
S fwd;
S bwd;
std::uint64_t rnd = 0;
int ls = -1;
int rs = -1;
int sz = 1;
bool rev = false;
};
std::vector<node> tr;
int rt = -1;
implicit_treap() = default;
explicit implicit_treap(const std::vector<S> &a) {
tr.reserve(a.size());
for (const S &val : a) {
rt = merge(rt, make_node(val));
}
}
int size() const { return node_size(rt); }
bool empty() const { return rt == -1; }
/// @brief Insert value immediately before position.
void insert(int pos, const S &val) {
assert(0 <= pos && pos <= size());
auto [l, r] = split(rt, pos);
rt = merge(merge(l, make_node(val)), r);
}
/// @brief Erase and return the value at position.
S erase(int pos) {
assert(0 <= pos && pos < size());
auto [l, suf] = split(rt, pos);
auto [mid, r] = split(suf, 1);
assert(mid != -1);
S val = tr[mid].val;
rt = merge(l, r);
return val;
}
/// @brief Replace the value at position.
void set(int pos, const S &val) {
assert(0 <= pos && pos < size());
auto [l, suf] = split(rt, pos);
auto [mid, r] = split(suf, 1);
tr[mid].val = val;
pull(mid);
rt = merge(l, merge(mid, r));
}
/// @brief Return the value at position.
S get(int pos) {
assert(0 <= pos && pos < size());
int cur = rt;
while (cur != -1) {
push(cur);
int lsz = node_size(tr[cur].ls);
if (pos < lsz) {
cur = tr[cur].ls;
} else if (pos == lsz) {
return tr[cur].val;
} else {
pos -= lsz + 1;
cur = tr[cur].rs;
}
}
assert(false);
return e();
}
/// @brief Reverse the half-open range [l, r).
void reverse(int l, int r) {
check_range(l, r);
auto [pre, suf] = split(rt, l);
auto [mid, tl] = split(suf, r - l);
apply_reverse(mid);
rt = merge(pre, merge(mid, tl));
}
/// @brief Return the ordered monoid product over [l, r).
S prod(int l, int r) {
check_range(l, r);
auto [pre, suf] = split(rt, l);
auto [mid, tl] = split(suf, r - l);
S res = forward_product(mid);
rt = merge(pre, merge(mid, tl));
return res;
}
/// @brief Materialize the current sequence.
std::vector<S> to_vector() {
std::vector<S> res;
res.reserve(size());
auto dfs = [&](auto &f, int cur) -> void {
if (cur == -1) {
return;
}
push(cur);
f(f, tr[cur].ls);
res.push_back(tr[cur].val);
f(f, tr[cur].rs);
};
dfs(dfs, rt);
return res;
}
private:
std::uint64_t rng = 0x243f6a8885a308d3ULL;
int node_size(int cur) const { return cur == -1 ? 0 : tr[cur].sz; }
S forward_product(int cur) const { return cur == -1 ? e() : tr[cur].fwd; }
S backward_product(int cur) const { return cur == -1 ? e() : tr[cur].bwd; }
std::uint64_t next_priority() {
std::uint64_t val = (rng += 0x9e3779b97f4a7c15ULL);
val = (val ^ (val >> 30)) * 0xbf58476d1ce4e5b9ULL;
val = (val ^ (val >> 27)) * 0x94d049bb133111ebULL;
return val ^ (val >> 31);
}
int make_node(const S &val) {
tr.push_back({val, val, val, next_priority()});
return int(tr.size()) - 1;
}
void apply_reverse(int cur) {
if (cur == -1) {
return;
}
std::swap(tr[cur].ls, tr[cur].rs);
std::swap(tr[cur].fwd, tr[cur].bwd);
tr[cur].rev = !tr[cur].rev;
}
void push(int cur) {
if (cur != -1 && tr[cur].rev) {
apply_reverse(tr[cur].ls);
apply_reverse(tr[cur].rs);
tr[cur].rev = false;
}
}
void pull(int cur) {
tr[cur].sz = 1 + node_size(tr[cur].ls) + node_size(tr[cur].rs);
tr[cur].fwd = op(op(forward_product(tr[cur].ls), tr[cur].val),
forward_product(tr[cur].rs));
tr[cur].bwd = op(op(backward_product(tr[cur].rs), tr[cur].val),
backward_product(tr[cur].ls));
}
std::pair<int, int> split(int cur, int lsz) {
if (cur == -1) {
return {-1, -1};
}
push(cur);
if (node_size(tr[cur].ls) >= lsz) {
auto [l, r] = split(tr[cur].ls, lsz);
tr[cur].ls = r;
pull(cur);
return {l, cur};
}
auto [l, r] = split(tr[cur].rs, lsz - node_size(tr[cur].ls) - 1);
tr[cur].rs = l;
pull(cur);
return {cur, r};
}
int merge(int l, int r) {
if (l == -1 || r == -1) {
return l == -1 ? r : l;
}
if (tr[l].rnd > tr[r].rnd) {
push(l);
tr[l].rs = merge(tr[l].rs, r);
pull(l);
return l;
}
push(r);
tr[r].ls = merge(l, tr[r].ls);
pull(r);
return r;
}
void check_range(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
}
};
} // namespace noya
#endif // NOYA_IMPLICIT_TREAP_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <vector>
/// @complexity Time: Expected O(log n) per split/merge/update/query.
/// Space: O(n) nodes and O(log n) expected stack.
namespace noya {
/// @brief Implicit randomized treap supporting insertion, erasure, reversal,
/// point updates, and ordered monoid products in expected O(log n) time.
template <class S, auto op, auto e> struct implicit_treap {
struct node {
S val;
S fwd;
S bwd;
std::uint64_t rnd = 0;
int ls = -1;
int rs = -1;
int sz = 1;
bool rev = false;
};
std::vector<node> tr;
int rt = -1;
implicit_treap() = default;
explicit implicit_treap(const std::vector<S> &a) {
tr.reserve(a.size());
for (const S &val : a) {
rt = merge(rt, make_node(val));
}
}
int size() const { return node_size(rt); }
bool empty() const { return rt == -1; }
/// @brief Insert value immediately before position.
void insert(int pos, const S &val) {
assert(0 <= pos && pos <= size());
auto [l, r] = split(rt, pos);
rt = merge(merge(l, make_node(val)), r);
}
/// @brief Erase and return the value at position.
S erase(int pos) {
assert(0 <= pos && pos < size());
auto [l, suf] = split(rt, pos);
auto [mid, r] = split(suf, 1);
assert(mid != -1);
S val = tr[mid].val;
rt = merge(l, r);
return val;
}
/// @brief Replace the value at position.
void set(int pos, const S &val) {
assert(0 <= pos && pos < size());
auto [l, suf] = split(rt, pos);
auto [mid, r] = split(suf, 1);
tr[mid].val = val;
pull(mid);
rt = merge(l, merge(mid, r));
}
/// @brief Return the value at position.
S get(int pos) {
assert(0 <= pos && pos < size());
int cur = rt;
while (cur != -1) {
push(cur);
int lsz = node_size(tr[cur].ls);
if (pos < lsz) {
cur = tr[cur].ls;
} else if (pos == lsz) {
return tr[cur].val;
} else {
pos -= lsz + 1;
cur = tr[cur].rs;
}
}
assert(false);
return e();
}
/// @brief Reverse the half-open range [l, r).
void reverse(int l, int r) {
check_range(l, r);
auto [pre, suf] = split(rt, l);
auto [mid, tl] = split(suf, r - l);
apply_reverse(mid);
rt = merge(pre, merge(mid, tl));
}
/// @brief Return the ordered monoid product over [l, r).
S prod(int l, int r) {
check_range(l, r);
auto [pre, suf] = split(rt, l);
auto [mid, tl] = split(suf, r - l);
S res = forward_product(mid);
rt = merge(pre, merge(mid, tl));
return res;
}
/// @brief Materialize the current sequence.
std::vector<S> to_vector() {
std::vector<S> res;
res.reserve(size());
auto dfs = [&](auto &f, int cur) -> void {
if (cur == -1) {
return;
}
push(cur);
f(f, tr[cur].ls);
res.push_back(tr[cur].val);
f(f, tr[cur].rs);
};
dfs(dfs, rt);
return res;
}
private:
std::uint64_t rng = 0x243f6a8885a308d3ULL;
int node_size(int cur) const { return cur == -1 ? 0 : tr[cur].sz; }
S forward_product(int cur) const { return cur == -1 ? e() : tr[cur].fwd; }
S backward_product(int cur) const { return cur == -1 ? e() : tr[cur].bwd; }
std::uint64_t next_priority() {
std::uint64_t val = (rng += 0x9e3779b97f4a7c15ULL);
val = (val ^ (val >> 30)) * 0xbf58476d1ce4e5b9ULL;
val = (val ^ (val >> 27)) * 0x94d049bb133111ebULL;
return val ^ (val >> 31);
}
int make_node(const S &val) {
tr.push_back({val, val, val, next_priority()});
return int(tr.size()) - 1;
}
void apply_reverse(int cur) {
if (cur == -1) {
return;
}
std::swap(tr[cur].ls, tr[cur].rs);
std::swap(tr[cur].fwd, tr[cur].bwd);
tr[cur].rev = !tr[cur].rev;
}
void push(int cur) {
if (cur != -1 && tr[cur].rev) {
apply_reverse(tr[cur].ls);
apply_reverse(tr[cur].rs);
tr[cur].rev = false;
}
}
void pull(int cur) {
tr[cur].sz = 1 + node_size(tr[cur].ls) + node_size(tr[cur].rs);
tr[cur].fwd = op(op(forward_product(tr[cur].ls), tr[cur].val),
forward_product(tr[cur].rs));
tr[cur].bwd = op(op(backward_product(tr[cur].rs), tr[cur].val),
backward_product(tr[cur].ls));
}
std::pair<int, int> split(int cur, int lsz) {
if (cur == -1) {
return {-1, -1};
}
push(cur);
if (node_size(tr[cur].ls) >= lsz) {
auto [l, r] = split(tr[cur].ls, lsz);
tr[cur].ls = r;
pull(cur);
return {l, cur};
}
auto [l, r] = split(tr[cur].rs, lsz - node_size(tr[cur].ls) - 1);
tr[cur].rs = l;
pull(cur);
return {cur, r};
}
int merge(int l, int r) {
if (l == -1 || r == -1) {
return l == -1 ? r : l;
}
if (tr[l].rnd > tr[r].rnd) {
push(l);
tr[l].rs = merge(tr[l].rs, r);
pull(l);
return l;
}
push(r);
tr[r].ls = merge(l, tr[r].ls);
pull(r);
return r;
}
void check_range(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
}
};
} // namespace noya