implicit_lazy_treap.hpp¶
在隐式 Treap 序列上增加区间懒操作和翻转；适合需要剪切、拼接并批量修改子段的动态序列。
Complexity: Time: \(O(n)\) construction; expected \(O(\log n)\) per insertion, erasure, reversal, range update, or range product, for \(O(1)\) monoid/actions. Space: \(O(a)\) allocated nodes (including erased nodes), \(O(n)\) build workspace and \(O(\log n)\) expected operation stack; \(a\) counts all nodes ever created.
AC 记录：dynamic_sequence_range_affine_range_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n) construction; expected O(log n) per insertion,
/// erasure, reversal, range update, or range product, for O(1) monoid/actions.
/// Space: O(a) allocated nodes (including erased nodes), O(n) build workspace
/// and O(log n) expected operation stack; a counts all nodes ever created.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
/// @brief Implicit randomized treap with reversible monoid products and lazy
/// range actions. Each node stores both product orders, so reversing a range
/// only swaps its children and its forward/backward aggregates. A pending
/// action is composed at a subtree root and pushed only before structural
/// changes, which keeps every sequence operation logarithmic in expectation.
template <class S, class F, auto op, auto e, auto mapping, auto composition,
auto id>
struct implicit_lazy_treap {
struct node {
S val;
S fwd;
S bwd;
F lz;
std::uint64_t rnd;
int ls = -1;
int rs = -1;
int sz = 1;
bool rev = false;
};
std::vector<node> tr;
int rt = -1;
implicit_lazy_treap() = default;
explicit implicit_lazy_treap(const std::vector<S> &a) {
tr.reserve(a.size());
std::vector<int> path;
path.reserve(a.size());
for (const S &val : a) {
int cur = make_node(val), last = -1;
// The path is the right spine of the Cartesian tree built so far.
while (!path.empty() && tr[path.back()].rnd <= tr[cur].rnd) {
last = path.back();
path.pop_back();
pull(last);
}
tr[cur].ls = last;
if (path.empty())
rt = cur;
else
tr[path.back()].rs = cur;
path.push_back(cur);
}
while (!path.empty()) {
pull(path.back());
path.pop_back();
}
}
int size() const { return node_size(rt); }
bool empty() const { return rt == -1; }
void reserve(int cap) { tr.reserve(cap); }
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);
}
S erase(int pos) {
assert(0 <= pos && pos < size());
auto [l, suf] = split(rt, pos);
auto [mid, r] = split(suf, 1);
push(mid);
S res = tr[mid].val;
rt = merge(l, r);
return res;
}
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));
}
void apply(int l, int r, const F &tag) {
check_range(l, r);
auto [pre, suf] = split(rt, l);
auto [mid, tl] = split(suf, r - l);
apply_action(mid, tag);
rt = merge(pre, merge(mid, tl));
}
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 = aggregate(mid, false);
rt = merge(pre, merge(mid, tl));
return res;
}
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 aggregate(int cur, bool bwd) const {
if (cur == -1) {
return e();
}
return bwd ? tr[cur].bwd : tr[cur].fwd;
}
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, id(), next_priority(), -1, -1, 1, false});
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 apply_action(int cur, const F &tag) {
if (cur == -1) {
return;
}
tr[cur].val = mapping(tag, tr[cur].val);
tr[cur].fwd = mapping(tag, tr[cur].fwd);
tr[cur].bwd = mapping(tag, tr[cur].bwd);
tr[cur].lz = composition(tag, tr[cur].lz);
}
void push(int cur) {
if (cur == -1) {
return;
}
if (tr[cur].rev) {
apply_reverse(tr[cur].ls);
apply_reverse(tr[cur].rs);
tr[cur].rev = false;
}
apply_action(tr[cur].ls, tr[cur].lz);
apply_action(tr[cur].rs, tr[cur].lz);
tr[cur].lz = id();
}
void pull(int cur) {
tr[cur].sz = 1 + node_size(tr[cur].ls) + node_size(tr[cur].rs);
tr[cur].fwd = op(op(aggregate(tr[cur].ls, false), tr[cur].val),
aggregate(tr[cur].rs, false));
tr[cur].bwd = op(op(aggregate(tr[cur].rs, true), tr[cur].val),
aggregate(tr[cur].ls, true));
}
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
// NOYA_IMPLICIT_LAZY_TREAP_HPP
#ifndef NOYA_IMPLICIT_LAZY_TREAP_HPP
#define NOYA_IMPLICIT_LAZY_TREAP_HPP 1
/// @complexity Time: O(n) construction; expected O(log n) per insertion,
/// erasure, reversal, range update, or range product, for O(1) monoid/actions.
/// Space: O(a) allocated nodes (including erased nodes), O(n) build workspace
/// and O(log n) expected operation stack; a counts all nodes ever created.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
/// @brief Implicit randomized treap with reversible monoid products and lazy
/// range actions. Each node stores both product orders, so reversing a range
/// only swaps its children and its forward/backward aggregates. A pending
/// action is composed at a subtree root and pushed only before structural
/// changes, which keeps every sequence operation logarithmic in expectation.
template <class S, class F, auto op, auto e, auto mapping, auto composition,
auto id>
struct implicit_lazy_treap {
struct node {
S val;
S fwd;
S bwd;
F lz;
std::uint64_t rnd;
int ls = -1;
int rs = -1;
int sz = 1;
bool rev = false;
};
std::vector<node> tr;
int rt = -1;
implicit_lazy_treap() = default;
explicit implicit_lazy_treap(const std::vector<S> &a) {
tr.reserve(a.size());
std::vector<int> path;
path.reserve(a.size());
for (const S &val : a) {
int cur = make_node(val), last = -1;
// The path is the right spine of the Cartesian tree built so far.
while (!path.empty() && tr[path.back()].rnd <= tr[cur].rnd) {
last = path.back();
path.pop_back();
pull(last);
}
tr[cur].ls = last;
if (path.empty())
rt = cur;
else
tr[path.back()].rs = cur;
path.push_back(cur);
}
while (!path.empty()) {
pull(path.back());
path.pop_back();
}
}
int size() const { return node_size(rt); }
bool empty() const { return rt == -1; }
void reserve(int cap) { tr.reserve(cap); }
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);
}
S erase(int pos) {
assert(0 <= pos && pos < size());
auto [l, suf] = split(rt, pos);
auto [mid, r] = split(suf, 1);
push(mid);
S res = tr[mid].val;
rt = merge(l, r);
return res;
}
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));
}
void apply(int l, int r, const F &tag) {
check_range(l, r);
auto [pre, suf] = split(rt, l);
auto [mid, tl] = split(suf, r - l);
apply_action(mid, tag);
rt = merge(pre, merge(mid, tl));
}
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 = aggregate(mid, false);
rt = merge(pre, merge(mid, tl));
return res;
}
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 aggregate(int cur, bool bwd) const {
if (cur == -1) {
return e();
}
return bwd ? tr[cur].bwd : tr[cur].fwd;
}
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, id(), next_priority(), -1, -1, 1, false});
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 apply_action(int cur, const F &tag) {
if (cur == -1) {
return;
}
tr[cur].val = mapping(tag, tr[cur].val);
tr[cur].fwd = mapping(tag, tr[cur].fwd);
tr[cur].bwd = mapping(tag, tr[cur].bwd);
tr[cur].lz = composition(tag, tr[cur].lz);
}
void push(int cur) {
if (cur == -1) {
return;
}
if (tr[cur].rev) {
apply_reverse(tr[cur].ls);
apply_reverse(tr[cur].rs);
tr[cur].rev = false;
}
apply_action(tr[cur].ls, tr[cur].lz);
apply_action(tr[cur].rs, tr[cur].lz);
tr[cur].lz = id();
}
void pull(int cur) {
tr[cur].sz = 1 + node_size(tr[cur].ls) + node_size(tr[cur].rs);
tr[cur].fwd = op(op(aggregate(tr[cur].ls, false), tr[cur].val),
aggregate(tr[cur].rs, false));
tr[cur].bwd = op(op(aggregate(tr[cur].rs, true), tr[cur].val),
aggregate(tr[cur].ls, true));
}
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_LAZY_TREAP_HPP
/// @complexity Time: O(n) construction; expected O(log n) per insertion,
/// erasure, reversal, range update, or range product, for O(1) monoid/actions.
/// Space: O(a) allocated nodes (including erased nodes), O(n) build workspace
/// and O(log n) expected operation stack; a counts all nodes ever created.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
/// @brief Implicit randomized treap with reversible monoid products and lazy
/// range actions. Each node stores both product orders, so reversing a range
/// only swaps its children and its forward/backward aggregates. A pending
/// action is composed at a subtree root and pushed only before structural
/// changes, which keeps every sequence operation logarithmic in expectation.
template <class S, class F, auto op, auto e, auto mapping, auto composition,
auto id>
struct implicit_lazy_treap {
struct node {
S val;
S fwd;
S bwd;
F lz;
std::uint64_t rnd;
int ls = -1;
int rs = -1;
int sz = 1;
bool rev = false;
};
std::vector<node> tr;
int rt = -1;
implicit_lazy_treap() = default;
explicit implicit_lazy_treap(const std::vector<S> &a) {
tr.reserve(a.size());
std::vector<int> path;
path.reserve(a.size());
for (const S &val : a) {
int cur = make_node(val), last = -1;
// The path is the right spine of the Cartesian tree built so far.
while (!path.empty() && tr[path.back()].rnd <= tr[cur].rnd) {
last = path.back();
path.pop_back();
pull(last);
}
tr[cur].ls = last;
if (path.empty())
rt = cur;
else
tr[path.back()].rs = cur;
path.push_back(cur);
}
while (!path.empty()) {
pull(path.back());
path.pop_back();
}
}
int size() const { return node_size(rt); }
bool empty() const { return rt == -1; }
void reserve(int cap) { tr.reserve(cap); }
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);
}
S erase(int pos) {
assert(0 <= pos && pos < size());
auto [l, suf] = split(rt, pos);
auto [mid, r] = split(suf, 1);
push(mid);
S res = tr[mid].val;
rt = merge(l, r);
return res;
}
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));
}
void apply(int l, int r, const F &tag) {
check_range(l, r);
auto [pre, suf] = split(rt, l);
auto [mid, tl] = split(suf, r - l);
apply_action(mid, tag);
rt = merge(pre, merge(mid, tl));
}
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 = aggregate(mid, false);
rt = merge(pre, merge(mid, tl));
return res;
}
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 aggregate(int cur, bool bwd) const {
if (cur == -1) {
return e();
}
return bwd ? tr[cur].bwd : tr[cur].fwd;
}
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, id(), next_priority(), -1, -1, 1, false});
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 apply_action(int cur, const F &tag) {
if (cur == -1) {
return;
}
tr[cur].val = mapping(tag, tr[cur].val);
tr[cur].fwd = mapping(tag, tr[cur].fwd);
tr[cur].bwd = mapping(tag, tr[cur].bwd);
tr[cur].lz = composition(tag, tr[cur].lz);
}
void push(int cur) {
if (cur == -1) {
return;
}
if (tr[cur].rev) {
apply_reverse(tr[cur].ls);
apply_reverse(tr[cur].rs);
tr[cur].rev = false;
}
apply_action(tr[cur].ls, tr[cur].lz);
apply_action(tr[cur].rs, tr[cur].lz);
tr[cur].lz = id();
}
void pull(int cur) {
tr[cur].sz = 1 + node_size(tr[cur].ls) + node_size(tr[cur].rs);
tr[cur].fwd = op(op(aggregate(tr[cur].ls, false), tr[cur].val),
aggregate(tr[cur].rs, false));
tr[cur].bwd = op(op(aggregate(tr[cur].rs, true), tr[cur].val),
aggregate(tr[cur].ls, true));
}
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
// NOYA_IMPLICIT_LAZY_TREAP_HPP