treap
| 投稿者 | askr58 |
|---|---|
| 言語 | C++23 |
| 更新日時 (JST) | 2026-10-17 20:58:31 |
| サイズ | 84,438 Byte |
| 参照URL | |
日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。
// generated by ChatGPT outside of contest time.
namespace implicit_treap_detail {
template <class S>
S disabled_op(S, S) {
std::abort();
}
template <class S>
S disabled_e() {
std::abort();
}
template <class S, class F>
S disabled_mapping(F, S) {
std::abort();
}
template <class F>
F disabled_composition(F, F) {
std::abort();
}
template <class F>
F disabled_id() {
std::abort();
}
// aggregate を使わないときは空クラス
template <class S, bool Enabled>
struct aggregate_storage {
explicit aggregate_storage(const S&) {}
};
template <class S>
struct aggregate_storage<S, true> {
S fwd, bwd;
explicit aggregate_storage(const S& x)
: fwd(x), bwd(x) {}
};
// lazy を使わないときは空クラス
template <class F, bool Enabled, F (*Id)()>
struct lazy_storage {
lazy_storage() = default;
};
template <class F, F (*Id)()>
struct lazy_storage<F, true, Id> {
F tag;
bool pending = false;
lazy_storage() : tag(Id()) {}
};
} // namespace implicit_treap_detail
template <
class S,
S (*op)(S, S)
= implicit_treap_detail::disabled_op<S>,
S (*e)()
= implicit_treap_detail::disabled_e<S>,
class F = S,
S (*mapping)(F, S)
= implicit_treap_detail::disabled_mapping<S, F>,
F (*composition)(F, F)
= implicit_treap_detail::disabled_composition<F>,
F (*id)()
= implicit_treap_detail::disabled_id<F>
>
class implicit_treap {
static constexpr int nil = -1;
static constexpr bool op_given =
op != implicit_treap_detail::disabled_op<S>;
static constexpr bool e_given =
e != implicit_treap_detail::disabled_e<S>;
static constexpr bool mapping_given =
mapping != implicit_treap_detail::disabled_mapping<S, F>;
static constexpr bool composition_given =
composition != implicit_treap_detail::disabled_composition<F>;
static constexpr bool id_given =
id != implicit_treap_detail::disabled_id<F>;
public:
static constexpr bool has_monoid =
op_given && e_given;
static constexpr bool has_lazy =
mapping_given && composition_given && id_given;
private:
static_assert(
op_given == e_given,
"implicit_treap: op and e must be specified together"
);
static_assert(
mapping_given == composition_given &&
composition_given == id_given,
"implicit_treap: mapping, composition and id "
"must be specified together"
);
static_assert(
!has_lazy || has_monoid,
"implicit_treap: lazy action requires op/e"
);
using Agg =
implicit_treap_detail::aggregate_storage<
S, has_monoid
>;
using Lazy =
implicit_treap_detail::lazy_storage<
F, has_lazy, id
>;
struct Node {
int l = nil;
int r = nil;
int sz = 1;
uint64_t pri = 0;
bool rev = false;
S val;
[[no_unique_address]]
Agg agg;
[[no_unique_address]]
Lazy lazy;
Node(S x, uint64_t p)
: pri(p),
val(std::move(x)),
agg(val),
lazy() {}
};
public:
class sequence {
friend class implicit_treap;
implicit_treap* owner_ = nullptr;
int root_ = nil;
sequence(
implicit_treap* owner,
int root
)
: owner_(owner),
root_(root) {}
void check_owner() const {
assert(owner_ != nullptr);
}
void release() {
if (owner_ && root_ != nil) {
owner_->release_tree(root_);
}
root_ = nil;
}
public:
sequence() = default;
sequence(const sequence&) = delete;
sequence& operator=(const sequence&) = delete;
sequence(sequence&& other) noexcept
: owner_(other.owner_),
root_(other.root_) {
other.owner_ = nullptr;
other.root_ = nil;
}
sequence& operator=(sequence&& other) noexcept {
if (this == &other) {
return *this;
}
release();
owner_ = other.owner_;
root_ = other.root_;
other.owner_ = nullptr;
other.root_ = nil;
return *this;
}
~sequence() {
release();
}
// ------------------------------------------------------------
// basic
// ------------------------------------------------------------
int size() const {
check_owner();
return owner_->node_size(root_);
}
bool empty() const {
return size() == 0;
}
void clear() {
check_owner();
release();
}
// ------------------------------------------------------------
// ACL: set / get
// ------------------------------------------------------------
void set(int p, S x) {
check_owner();
assert(
0 <= p &&
p < size()
);
owner_->set_impl(
root_,
p,
std::move(x)
);
}
S get(int p) {
check_owner();
assert(
0 <= p &&
p < size()
);
return owner_->get_impl(
root_,
p
);
}
// ------------------------------------------------------------
// to_vector
//
// to_vector() : 列全体
// to_vector(l, r) : [l, r)
//
// 計算量:
// expected O(log n + (r - l))
// 全体なら O(n)
// ------------------------------------------------------------
std::vector<S> to_vector() {
check_owner();
std::vector<S> res;
res.reserve(size());
owner_->to_vector_impl(
root_,
0,
size(),
res
);
return res;
}
std::vector<S> to_vector(int l, int r) {
check_owner();
assert(
0 <= l &&
l <= r &&
r <= size()
);
std::vector<S> res;
res.reserve(r - l);
owner_->to_vector_impl(
root_,
l,
r,
res
);
return res;
}
// ------------------------------------------------------------
// ACL: prod / all_prod
// ------------------------------------------------------------
S prod(int l, int r) {
check_owner();
if constexpr (!has_monoid) {
assert(
has_monoid &&
"implicit_treap::prod requires op/e"
);
std::abort();
} else {
assert(
0 <= l &&
l <= r &&
r <= size()
);
return owner_->prod_impl(
root_,
l,
r
);
}
}
S all_prod() const {
check_owner();
if constexpr (!has_monoid) {
assert(
has_monoid &&
"implicit_treap::all_prod requires op/e"
);
std::abort();
} else {
return root_ == nil
? e()
: owner_->nodes_[root_].agg.fwd;
}
}
// ------------------------------------------------------------
// ACL: apply
// ------------------------------------------------------------
void apply(int p, F f) {
check_owner();
if constexpr (!has_lazy) {
assert(
has_lazy &&
"implicit_treap::apply requires "
"mapping/composition/id"
);
std::abort();
} else {
assert(
0 <= p &&
p < size()
);
owner_->apply_point_impl(
root_,
p,
f
);
}
}
void apply(int l, int r, F f) {
check_owner();
if constexpr (!has_lazy) {
assert(
has_lazy &&
"implicit_treap::apply requires "
"mapping/composition/id"
);
std::abort();
} else {
assert(
0 <= l &&
l <= r &&
r <= size()
);
owner_->apply_range_impl(
root_,
l,
r,
f
);
}
}
// ------------------------------------------------------------
// ACL: max_right
// ------------------------------------------------------------
template <class G>
int max_right(int l, G g) {
check_owner();
if constexpr (!has_monoid) {
assert(
has_monoid &&
"implicit_treap::max_right requires op/e"
);
std::abort();
} else {
assert(
0 <= l &&
l <= size()
);
S sm = e();
assert(
std::invoke(g, sm)
);
if (l == size()) {
return size();
}
return owner_->max_right_impl(
root_,
l,
sm,
g
);
}
}
// ACL と同じ max_right<g>(l) 形式
template <bool (*g)(S)>
int max_right(int l) {
return max_right(l, g);
}
// ------------------------------------------------------------
// ACL: min_left
// ------------------------------------------------------------
template <class G>
int min_left(int r, G g) {
check_owner();
if constexpr (!has_monoid) {
assert(
has_monoid &&
"implicit_treap::min_left requires op/e"
);
std::abort();
} else {
assert(
0 <= r &&
r <= size()
);
S sm = e();
assert(
std::invoke(g, sm)
);
if (r == 0) {
return 0;
}
return owner_->min_left_impl(
root_,
r,
sm,
g
);
}
}
template <bool (*g)(S)>
int min_left(int r) {
return min_left(r, g);
}
// ------------------------------------------------------------
// insert / erase
// ------------------------------------------------------------
void insert(int k, S x) {
check_owner();
assert(
0 <= k &&
k <= size()
);
int v =
owner_->new_node(
std::move(x)
);
auto [a, b] =
owner_->split_root(
root_,
k
);
root_ =
owner_->merge_root(
owner_->merge_root(
a,
v
),
b
);
}
void erase(int k) {
check_owner();
assert(
0 <= k &&
k < size()
);
auto [a, bc] =
owner_->split_root(
root_,
k
);
auto [b, c] =
owner_->split_root(
bc,
1
);
assert(
owner_->node_size(b) == 1
);
owner_->release_node(b);
root_ =
owner_->merge_root(
a,
c
);
}
// ------------------------------------------------------------
// reverse [l, r)
// ------------------------------------------------------------
void reverse(int l, int r) {
check_owner();
assert(
0 <= l &&
l <= r &&
r <= size()
);
if (l == r) {
return;
}
auto [a, bc] =
owner_->split_root(
root_,
l
);
auto [b, c] =
owner_->split_root(
bc,
r - l
);
owner_->toggle_reverse(b);
root_ =
owner_->merge_root(
owner_->merge_root(
a,
b
),
c
);
}
// ------------------------------------------------------------
// split
//
// *this は空になる。
// ------------------------------------------------------------
std::pair<sequence, sequence>
split(int k) {
check_owner();
assert(
0 <= k &&
k <= size()
);
auto [a, b] =
owner_->split_root(
root_,
k
);
root_ = nil;
return {
sequence(owner_, a),
sequence(owner_, b)
};
}
// ------------------------------------------------------------
// merge
//
// rhs を末尾に連結。
// rhs は move-consume される。
// ------------------------------------------------------------
sequence&
merge(sequence&& rhs) {
check_owner();
rhs.check_owner();
assert(
this != &rhs
);
assert(
owner_ == rhs.owner_ &&
"cannot merge sequences "
"from different pools"
);
root_ =
owner_->merge_root(
root_,
rhs.root_
);
rhs.root_ = nil;
rhs.owner_ = nullptr;
return *this;
}
// ------------------------------------------------------------
// lower_bound
//
// ranges::lower_bound 相当。
//
// 列が
// comp(proj(x_i), proj(x_j))
// に関してソート済みであることを仮定。
//
// projection は列要素だけに適用する点も
// std::ranges と同じ。
// ------------------------------------------------------------
template <
class T,
class Comp = std::ranges::less,
class Proj = std::identity
>
int lower_bound(
const T& value,
Comp comp = {},
Proj proj = {}
) {
check_owner();
int t = root_;
int base = 0;
int ans = size();
while (t != nil) {
owner_->push(t);
int ls =
owner_->node_size(
owner_->nodes_[t].l
);
int idx =
base + ls;
if (
std::invoke(
comp,
std::invoke(
proj,
owner_->nodes_[t].val
),
value
)
) {
base = idx + 1;
t = owner_->nodes_[t].r;
} else {
ans = idx;
t = owner_->nodes_[t].l;
}
}
return ans;
}
// ------------------------------------------------------------
// upper_bound
//
// ranges::upper_bound 相当。
// ------------------------------------------------------------
template <
class T,
class Comp = std::ranges::less,
class Proj = std::identity
>
int upper_bound(
const T& value,
Comp comp = {},
Proj proj = {}
) {
check_owner();
int t = root_;
int base = 0;
int ans = size();
while (t != nil) {
owner_->push(t);
int ls =
owner_->node_size(
owner_->nodes_[t].l
);
int idx =
base + ls;
if (
!std::invoke(
comp,
value,
std::invoke(
proj,
owner_->nodes_[t].val
)
)
) {
base = idx + 1;
t = owner_->nodes_[t].r;
} else {
ans = idx;
t = owner_->nodes_[t].l;
}
}
return ans;
}
};
private:
int max_nodes_;
std::vector<Node> nodes_;
std::vector<int> free_;
uint64_t rng_state_;
// ------------------------------------------------------------
// RNG
// ------------------------------------------------------------
static uint64_t default_seed() {
return
uint64_t(
std::chrono::steady_clock::now()
.time_since_epoch()
.count()
)
^
uint64_t(
reinterpret_cast<uintptr_t>(
&default_seed
)
);
}
uint64_t rng() {
uint64_t z =
(
rng_state_
+= 0x9e3779b97f4a7c15ULL
);
z =
(z ^ (z >> 30))
* 0xbf58476d1ce4e5b9ULL;
z =
(z ^ (z >> 27))
* 0x94d049bb133111ebULL;
return
z ^ (z >> 31);
}
// ------------------------------------------------------------
// basic node utilities
// ------------------------------------------------------------
int node_size(int t) const {
return t == nil
? 0
: nodes_[t].sz;
}
bool higher(
int a,
int b
) const {
if (
nodes_[a].pri
!= nodes_[b].pri
) {
return
nodes_[a].pri
> nodes_[b].pri;
}
// priority collision を完全に処理
return a > b;
}
int new_node(S x) {
int v;
if (!free_.empty()) {
v = free_.back();
free_.pop_back();
nodes_[v] =
Node(
std::move(x),
rng()
);
} else {
assert(
static_cast<int>(
nodes_.size()
)
< max_nodes_
&&
"implicit_treap node pool exhausted"
);
v =
static_cast<int>(
nodes_.size()
);
nodes_.emplace_back(
std::move(x),
rng()
);
}
return v;
}
void release_node(int v) {
assert(v != nil);
free_.push_back(v);
}
// 部分木全体を freelist に返す。
// lazy を push する必要はない。
void release_tree(int root) {
if (root == nil) {
return;
}
std::vector<int> st{
root
};
while (!st.empty()) {
int v = st.back();
st.pop_back();
if (nodes_[v].l != nil) {
st.push_back(
nodes_[v].l
);
}
if (nodes_[v].r != nil) {
st.push_back(
nodes_[v].r
);
}
free_.push_back(v);
}
}
// ------------------------------------------------------------
// aggregate
// ------------------------------------------------------------
S fwd(int t) const {
return t == nil
? e()
: nodes_[t].agg.fwd;
}
S bwd(int t) const {
return t == nil
? e()
: nodes_[t].agg.bwd;
}
void pull(int t) {
Node& n =
nodes_[t];
n.sz =
node_size(n.l)
+ 1
+ node_size(n.r);
if constexpr (has_monoid) {
n.agg.fwd =
op(
op(
fwd(n.l),
n.val
),
fwd(n.r)
);
n.agg.bwd =
op(
op(
bwd(n.r),
n.val
),
bwd(n.l)
);
}
}
// ------------------------------------------------------------
// lazy
//
// composition(f, g) = f ∘ g
// ACL と同じ順序。
// ------------------------------------------------------------
void apply_all(
int t,
const F& f
) {
if (t == nil) {
return;
}
if constexpr (has_lazy) {
Node& n =
nodes_[t];
n.val =
mapping(
f,
n.val
);
n.agg.fwd =
mapping(
f,
n.agg.fwd
);
n.agg.bwd =
mapping(
f,
n.agg.bwd
);
if (n.lazy.pending) {
n.lazy.tag =
composition(
f,
n.lazy.tag
);
} else {
n.lazy.tag = f;
n.lazy.pending = true;
}
}
}
// ------------------------------------------------------------
// reverse
// ------------------------------------------------------------
void toggle_reverse(int t) {
if (t == nil) {
return;
}
Node& n =
nodes_[t];
std::swap(
n.l,
n.r
);
n.rev =
!n.rev;
if constexpr (has_monoid) {
std::swap(
n.agg.fwd,
n.agg.bwd
);
}
}
// ------------------------------------------------------------
// push
// ------------------------------------------------------------
void push(int t) {
if (t == nil) {
return;
}
Node& n =
nodes_[t];
if (n.rev) {
toggle_reverse(n.l);
toggle_reverse(n.r);
n.rev = false;
}
if constexpr (has_lazy) {
if (n.lazy.pending) {
F f =
n.lazy.tag;
apply_all(
n.l,
f
);
apply_all(
n.r,
f
);
n.lazy.pending = false;
n.lazy.tag = id();
}
}
}
// ------------------------------------------------------------
// split / merge core
// ------------------------------------------------------------
std::pair<int, int>
split_root(
int t,
int k
) {
if (t == nil) {
return {
nil,
nil
};
}
assert(
0 <= k &&
k <= node_size(t)
);
push(t);
int ls =
node_size(
nodes_[t].l
);
if (k <= ls) {
auto [a, b] =
split_root(
nodes_[t].l,
k
);
nodes_[t].l = b;
pull(t);
return {
a,
t
};
} else {
auto [a, b] =
split_root(
nodes_[t].r,
k - ls - 1
);
nodes_[t].r = a;
pull(t);
return {
t,
b
};
}
}
int merge_root(
int a,
int b
) {
if (a == nil) {
return b;
}
if (b == nil) {
return a;
}
if (higher(a, b)) {
push(a);
nodes_[a].r =
merge_root(
nodes_[a].r,
b
);
pull(a);
return a;
} else {
push(b);
nodes_[b].l =
merge_root(
a,
nodes_[b].l
);
pull(b);
return b;
}
}
// ------------------------------------------------------------
// set / get
// ------------------------------------------------------------
void set_impl(
int t,
int p,
S x
) {
push(t);
int ls =
node_size(
nodes_[t].l
);
if (p < ls) {
set_impl(
nodes_[t].l,
p,
std::move(x)
);
} else if (p == ls) {
nodes_[t].val =
std::move(x);
} else {
set_impl(
nodes_[t].r,
p - ls - 1,
std::move(x)
);
}
pull(t);
}
S get_impl(
int t,
int p
) {
while (true) {
push(t);
int ls =
node_size(
nodes_[t].l
);
if (p < ls) {
t =
nodes_[t].l;
} else if (p == ls) {
return
nodes_[t].val;
} else {
p -= ls + 1;
t =
nodes_[t].r;
}
}
}
// ------------------------------------------------------------
// to_vector
//
// subtree t の [l, r) を inorder で res に追加する。
// ------------------------------------------------------------
void to_vector_impl(
int t,
int l,
int r,
std::vector<S>& res
) {
if (
t == nil ||
l == r
) {
return;
}
assert(
0 <= l &&
l <= r &&
r <= node_size(t)
);
push(t);
int ls =
node_size(
nodes_[t].l
);
// 左部分木との共通部分
if (l < ls) {
to_vector_impl(
nodes_[t].l,
l,
std::min(r, ls),
res
);
}
// 自分自身
if (
l <= ls &&
ls < r
) {
res.push_back(
nodes_[t].val
);
}
// 右部分木との共通部分
if (r > ls + 1) {
int nl =
std::max(
0,
l - ls - 1
);
int nr =
r - ls - 1;
to_vector_impl(
nodes_[t].r,
nl,
nr,
res
);
}
}
// ------------------------------------------------------------
// prod
// ------------------------------------------------------------
S prod_impl(
int t,
int l,
int r
) {
if (l == r) {
return e();
}
if (
l == 0 &&
r == node_size(t)
) {
return
nodes_[t].agg.fwd;
}
push(t);
int ls =
node_size(
nodes_[t].l
);
S res = e();
if (l < ls) {
res =
op(
res,
prod_impl(
nodes_[t].l,
l,
std::min(r, ls)
)
);
}
if (
l <= ls &&
ls < r
) {
res =
op(
res,
nodes_[t].val
);
}
if (r > ls + 1) {
int nl =
std::max(
0,
l - ls - 1
);
int nr =
r - ls - 1;
res =
op(
res,
prod_impl(
nodes_[t].r,
nl,
nr
)
);
}
return res;
}
// ------------------------------------------------------------
// point apply
// ------------------------------------------------------------
void apply_point_impl(
int t,
int p,
const F& f
) {
push(t);
int ls =
node_size(
nodes_[t].l
);
if (p < ls) {
apply_point_impl(
nodes_[t].l,
p,
f
);
} else if (p == ls) {
// subtree 全体ではなく
// この要素だけに mapping
nodes_[t].val =
mapping(
f,
nodes_[t].val
);
} else {
apply_point_impl(
nodes_[t].r,
p - ls - 1,
f
);
}
pull(t);
}
// ------------------------------------------------------------
// range apply
// ------------------------------------------------------------
void apply_range_impl(
int t,
int l,
int r,
const F& f
) {
if (
l == r ||
t == nil
) {
return;
}
if (
l == 0 &&
r == node_size(t)
) {
apply_all(
t,
f
);
return;
}
push(t);
int ls =
node_size(
nodes_[t].l
);
if (l < ls) {
apply_range_impl(
nodes_[t].l,
l,
std::min(r, ls),
f
);
}
if (
l <= ls &&
ls < r
) {
nodes_[t].val =
mapping(
f,
nodes_[t].val
);
}
if (r > ls + 1) {
int nl =
std::max(
0,
l - ls - 1
);
int nr =
r - ls - 1;
apply_range_impl(
nodes_[t].r,
nl,
nr,
f
);
}
pull(t);
}
// ------------------------------------------------------------
// max_right
// ------------------------------------------------------------
template <class G>
int max_right_impl(
int t,
int l,
S& sm,
G& g
) {
int n =
node_size(t);
if (
t == nil ||
l == n
) {
return n;
}
// subtree 全体を一発で取れる場合
if (l == 0) {
S cand =
op(
sm,
nodes_[t].agg.fwd
);
if (
std::invoke(
g,
cand
)
) {
sm =
std::move(cand);
return n;
}
}
push(t);
int ls =
node_size(
nodes_[t].l
);
if (l < ls) {
int x =
max_right_impl(
nodes_[t].l,
l,
sm,
g
);
if (x < ls) {
return x;
}
S cand =
op(
sm,
nodes_[t].val
);
if (
!std::invoke(
g,
cand
)
) {
return ls;
}
sm =
std::move(cand);
int y =
max_right_impl(
nodes_[t].r,
0,
sm,
g
);
return
ls + 1 + y;
}
if (l == ls) {
S cand =
op(
sm,
nodes_[t].val
);
if (
!std::invoke(
g,
cand
)
) {
return ls;
}
sm =
std::move(cand);
int y =
max_right_impl(
nodes_[t].r,
0,
sm,
g
);
return
ls + 1 + y;
}
int y =
max_right_impl(
nodes_[t].r,
l - ls - 1,
sm,
g
);
return
ls + 1 + y;
}
// ------------------------------------------------------------
// min_left
// ------------------------------------------------------------
template <class G>
int min_left_impl(
int t,
int r,
S& sm,
G& g
) {
int n =
node_size(t);
if (
t == nil ||
r == 0
) {
return 0;
}
// subtree 全体
if (r == n) {
S cand =
op(
nodes_[t].agg.fwd,
sm
);
if (
std::invoke(
g,
cand
)
) {
sm =
std::move(cand);
return 0;
}
}
push(t);
int ls =
node_size(
nodes_[t].l
);
if (r > ls + 1) {
int x =
min_left_impl(
nodes_[t].r,
r - ls - 1,
sm,
g
);
if (x > 0) {
return
ls + 1 + x;
}
S cand =
op(
nodes_[t].val,
sm
);
if (
!std::invoke(
g,
cand
)
) {
return
ls + 1;
}
sm =
std::move(cand);
return
min_left_impl(
nodes_[t].l,
ls,
sm,
g
);
}
if (r == ls + 1) {
S cand =
op(
nodes_[t].val,
sm
);
if (
!std::invoke(
g,
cand
)
) {
return
ls + 1;
}
sm =
std::move(cand);
return
min_left_impl(
nodes_[t].l,
ls,
sm,
g
);
}
return
min_left_impl(
nodes_[t].l,
r,
sm,
g
);
}
// ------------------------------------------------------------
// O(n) build
//
// priority から Cartesian Tree を構築。
// ------------------------------------------------------------
int build_from_vector(
std::vector<S> values
) {
if (values.empty()) {
return nil;
}
int active =
static_cast<int>(
nodes_.size()
)
-
static_cast<int>(
free_.size()
);
assert(
static_cast<int>(
values.size()
)
<= max_nodes_ - active
&&
"implicit_treap node pool exhausted"
);
std::vector<int> ids;
ids.reserve(
values.size()
);
for (auto& x : values) {
ids.push_back(
new_node(
std::move(x)
)
);
}
std::vector<int> st;
st.reserve(
ids.size()
);
for (int v : ids) {
int last = nil;
while (
!st.empty() &&
higher(
v,
st.back()
)
) {
last =
st.back();
st.pop_back();
}
nodes_[v].l =
last;
if (!st.empty()) {
nodes_[st.back()].r =
v;
}
st.push_back(v);
}
int root =
st.front();
// post-order pull
std::vector<int> order;
order.reserve(
ids.size()
);
std::vector<int> dfs{
root
};
while (!dfs.empty()) {
int v =
dfs.back();
dfs.pop_back();
order.push_back(v);
if (nodes_[v].l != nil) {
dfs.push_back(
nodes_[v].l
);
}
if (nodes_[v].r != nil) {
dfs.push_back(
nodes_[v].r
);
}
}
for (
auto it = order.rbegin();
it != order.rend();
++it
) {
pull(*it);
}
return root;
}
public:
// ------------------------------------------------------------
// pool constructor
// ------------------------------------------------------------
explicit implicit_treap(
int max_nodes,
uint64_t seed = default_seed()
)
: max_nodes_(max_nodes),
rng_state_(seed) {
assert(
max_nodes >= 0
);
nodes_.reserve(
max_nodes_
);
free_.reserve(
max_nodes_
);
}
implicit_treap(
const implicit_treap&
) = delete;
implicit_treap&
operator=(
const implicit_treap&
) = delete;
// ------------------------------------------------------------
// sequence construction
// ------------------------------------------------------------
sequence make_sequence() {
return
sequence(
this,
nil
);
}
sequence make_sequence(
std::vector<S> values
) {
return
sequence(
this,
build_from_vector(
std::move(values)
)
);
}
sequence make_sequence(
std::initializer_list<S> values
) {
return
make_sequence(
std::vector<S>(
values
)
);
}
// 短い alias
sequence make() {
return
make_sequence();
}
sequence make(
std::vector<S> values
) {
return
make_sequence(
std::move(values)
);
}
sequence make(
std::initializer_list<S> values
) {
return
make_sequence(values);
}
// ------------------------------------------------------------
// pool-level merge
//
// a,b を両方 consume して新しい sequence を返す。
// ------------------------------------------------------------
sequence merge(
sequence&& a,
sequence&& b
) {
assert(
&a != &b
);
a.check_owner();
b.check_owner();
assert(
a.owner_ == this &&
b.owner_ == this &&
"cannot merge sequences from different pools"
);
int ar =
a.root_;
int br =
b.root_;
a.root_ = nil;
b.root_ = nil;
a.owner_ = nullptr;
b.owner_ = nullptr;
return
sequence(
this,
merge_root(
ar,
br
)
);
}
// ------------------------------------------------------------
// pool-level split
// ------------------------------------------------------------
std::pair<sequence, sequence>
split(
sequence&& s,
int k
) {
s.check_owner();
assert(
s.owner_ == this
);
return
s.split(k);
}
// ------------------------------------------------------------
// pool information
// ------------------------------------------------------------
int capacity() const {
return max_nodes_;
}
int allocated_nodes() const {
return
static_cast<int>(
nodes_.size()
)
-
static_cast<int>(
free_.size()
);
}
};
// implicit_treap<S> pool(n);
// auto t=pool.make(vec);
// generated by ChatGPT outside of contest time.
namespace implicit_treap_detail {
template <class S>
S disabled_op(S, S) {
std::abort();
}
template <class S>
S disabled_e() {
std::abort();
}
template <class S, class F>
S disabled_mapping(F, S) {
std::abort();
}
template <class F>
F disabled_composition(F, F) {
std::abort();
}
template <class F>
F disabled_id() {
std::abort();
}
// aggregate を使わないときは空クラス
template <class S, bool Enabled>
struct aggregate_storage {
explicit aggregate_storage(const S&) {}
};
template <class S>
struct aggregate_storage<S, true> {
S prod;
explicit aggregate_storage(const S& x)
: prod(x) {}
};
// lazy を使わないときは空クラス
template <class F, bool Enabled, F (*Id)()>
struct lazy_storage {
lazy_storage() = default;
};
template <class F, F (*Id)()>
struct lazy_storage<F, true, Id> {
F tag;
bool pending = false;
lazy_storage() : tag(Id()) {}
};
} // namespace implicit_treap_detail
template <
class S,
S (*op)(S, S)
= implicit_treap_detail::disabled_op<S>,
S (*e)()
= implicit_treap_detail::disabled_e<S>,
class F = S,
S (*mapping)(F, S)
= implicit_treap_detail::disabled_mapping<S, F>,
F (*composition)(F, F)
= implicit_treap_detail::disabled_composition<F>,
F (*id)()
= implicit_treap_detail::disabled_id<F>
>
class implicit_treap {
static constexpr int nil = -1;
static constexpr bool op_given =
op != implicit_treap_detail::disabled_op<S>;
static constexpr bool e_given =
e != implicit_treap_detail::disabled_e<S>;
static constexpr bool mapping_given =
mapping != implicit_treap_detail::disabled_mapping<S, F>;
static constexpr bool composition_given =
composition != implicit_treap_detail::disabled_composition<F>;
static constexpr bool id_given =
id != implicit_treap_detail::disabled_id<F>;
public:
static constexpr bool has_monoid =
op_given && e_given;
static constexpr bool has_lazy =
mapping_given && composition_given && id_given;
private:
static_assert(
op_given == e_given,
"implicit_treap: op and e must be specified together"
);
static_assert(
mapping_given == composition_given &&
composition_given == id_given,
"implicit_treap: mapping, composition and id "
"must be specified together"
);
static_assert(
!has_lazy || has_monoid,
"implicit_treap: lazy action requires op/e"
);
using Agg =
implicit_treap_detail::aggregate_storage<
S, has_monoid
>;
using Lazy =
implicit_treap_detail::lazy_storage<
F, has_lazy, id
>;
struct Node {
int l = nil;
int r = nil;
int sz = 1;
uint64_t pri = 0;
S val;
[[no_unique_address]]
Agg agg;
[[no_unique_address]]
Lazy lazy;
Node(S x, uint64_t p)
: pri(p),
val(std::move(x)),
agg(val),
lazy() {}
};
public:
class sequence {
friend class implicit_treap;
implicit_treap* owner_ = nullptr;
int root_ = nil;
sequence(
implicit_treap* owner,
int root
)
: owner_(owner),
root_(root) {}
void check_owner() const {
assert(owner_ != nullptr);
}
void release() {
if (owner_ && root_ != nil) {
owner_->release_tree(root_);
}
root_ = nil;
}
public:
sequence() = default;
sequence(const sequence&) = delete;
sequence& operator=(const sequence&) = delete;
sequence(sequence&& other) noexcept
: owner_(other.owner_),
root_(other.root_) {
other.owner_ = nullptr;
other.root_ = nil;
}
sequence& operator=(sequence&& other) noexcept {
if (this == &other) {
return *this;
}
release();
owner_ = other.owner_;
root_ = other.root_;
other.owner_ = nullptr;
other.root_ = nil;
return *this;
}
~sequence() {
release();
}
// ------------------------------------------------------------
// basic
// ------------------------------------------------------------
int size() const {
check_owner();
return owner_->node_size(root_);
}
bool empty() const {
return size() == 0;
}
void clear() {
check_owner();
release();
}
// ------------------------------------------------------------
// ACL: set / get
// ------------------------------------------------------------
void set(int p, S x) {
check_owner();
assert(
0 <= p &&
p < size()
);
owner_->set_impl(
root_,
p,
std::move(x)
);
}
S get(int p) {
check_owner();
assert(
0 <= p &&
p < size()
);
return owner_->get_impl(
root_,
p
);
}
// ------------------------------------------------------------
// to_vector
//
// to_vector() : 列全体
// to_vector(l, r) : [l, r)
//
// 計算量:
// expected O(log n + (r - l))
// 全体なら O(n)
// ------------------------------------------------------------
std::vector<S> to_vector() {
check_owner();
std::vector<S> res;
res.reserve(size());
owner_->to_vector_impl(
root_,
0,
size(),
res
);
return res;
}
std::vector<S> to_vector(int l, int r) {
check_owner();
assert(
0 <= l &&
l <= r &&
r <= size()
);
std::vector<S> res;
res.reserve(r - l);
owner_->to_vector_impl(
root_,
l,
r,
res
);
return res;
}
// ------------------------------------------------------------
// ACL: prod / all_prod
// ------------------------------------------------------------
S prod(int l, int r) {
check_owner();
if constexpr (!has_monoid) {
assert(
has_monoid &&
"implicit_treap::prod requires op/e"
);
std::abort();
} else {
assert(
0 <= l &&
l <= r &&
r <= size()
);
return owner_->prod_impl(
root_,
l,
r
);
}
}
S all_prod() const {
check_owner();
if constexpr (!has_monoid) {
assert(
has_monoid &&
"implicit_treap::all_prod requires op/e"
);
std::abort();
} else {
return root_ == nil
? e()
: owner_->nodes_[root_].agg.prod;
}
}
// ------------------------------------------------------------
// ACL: apply
// ------------------------------------------------------------
void apply(int p, F f) {
check_owner();
if constexpr (!has_lazy) {
assert(
has_lazy &&
"implicit_treap::apply requires "
"mapping/composition/id"
);
std::abort();
} else {
assert(
0 <= p &&
p < size()
);
owner_->apply_point_impl(
root_,
p,
f
);
}
}
void apply(int l, int r, F f) {
check_owner();
if constexpr (!has_lazy) {
assert(
has_lazy &&
"implicit_treap::apply requires "
"mapping/composition/id"
);
std::abort();
} else {
assert(
0 <= l &&
l <= r &&
r <= size()
);
owner_->apply_range_impl(
root_,
l,
r,
f
);
}
}
// ------------------------------------------------------------
// ACL: max_right
// ------------------------------------------------------------
template <class G>
int max_right(int l, G g) {
check_owner();
if constexpr (!has_monoid) {
assert(
has_monoid &&
"implicit_treap::max_right requires op/e"
);
std::abort();
} else {
assert(
0 <= l &&
l <= size()
);
S sm = e();
assert(
std::invoke(g, sm)
);
if (l == size()) {
return size();
}
return owner_->max_right_impl(
root_,
l,
sm,
g
);
}
}
// ACL と同じ max_right<g>(l) 形式
template <bool (*g)(S)>
int max_right(int l) {
return max_right(l, g);
}
// ------------------------------------------------------------
// ACL: min_left
// ------------------------------------------------------------
template <class G>
int min_left(int r, G g) {
check_owner();
if constexpr (!has_monoid) {
assert(
has_monoid &&
"implicit_treap::min_left requires op/e"
);
std::abort();
} else {
assert(
0 <= r &&
r <= size()
);
S sm = e();
assert(
std::invoke(g, sm)
);
if (r == 0) {
return 0;
}
return owner_->min_left_impl(
root_,
r,
sm,
g
);
}
}
template <bool (*g)(S)>
int min_left(int r) {
return min_left(r, g);
}
// ------------------------------------------------------------
// insert / erase
// ------------------------------------------------------------
void insert(int k, S x) {
check_owner();
assert(
0 <= k &&
k <= size()
);
int v =
owner_->new_node(
std::move(x)
);
auto [a, b] =
owner_->split_root(
root_,
k
);
root_ =
owner_->merge_root(
owner_->merge_root(
a,
v
),
b
);
}
void erase(int k) {
check_owner();
assert(
0 <= k &&
k < size()
);
auto [a, bc] =
owner_->split_root(
root_,
k
);
auto [b, c] =
owner_->split_root(
bc,
1
);
assert(
owner_->node_size(b) == 1
);
owner_->release_node(b);
root_ =
owner_->merge_root(
a,
c
);
}
// ------------------------------------------------------------
// split
//
// *this は空になる。
// ------------------------------------------------------------
std::pair<sequence, sequence>
split(int k) {
check_owner();
assert(
0 <= k &&
k <= size()
);
auto [a, b] =
owner_->split_root(
root_,
k
);
root_ = nil;
return {
sequence(owner_, a),
sequence(owner_, b)
};
}
// ------------------------------------------------------------
// merge
//
// rhs を末尾に連結。
// rhs は move-consume される。
// ------------------------------------------------------------
sequence&
merge(sequence&& rhs) {
check_owner();
rhs.check_owner();
assert(
this != &rhs
);
assert(
owner_ == rhs.owner_ &&
"cannot merge sequences "
"from different pools"
);
root_ =
owner_->merge_root(
root_,
rhs.root_
);
rhs.root_ = nil;
rhs.owner_ = nullptr;
return *this;
}
// ------------------------------------------------------------
// lower_bound
//
// ranges::lower_bound 相当。
//
// 列が
// comp(proj(x_i), proj(x_j))
// に関してソート済みであることを仮定。
//
// projection は列要素だけに適用する点も
// std::ranges と同じ。
// ------------------------------------------------------------
template <
class T,
class Comp = std::ranges::less,
class Proj = std::identity
>
int lower_bound(
const T& value,
Comp comp = {},
Proj proj = {}
) {
check_owner();
int t = root_;
int base = 0;
int ans = size();
while (t != nil) {
owner_->push(t);
int ls =
owner_->node_size(
owner_->nodes_[t].l
);
int idx =
base + ls;
if (
std::invoke(
comp,
std::invoke(
proj,
owner_->nodes_[t].val
),
value
)
) {
base = idx + 1;
t = owner_->nodes_[t].r;
} else {
ans = idx;
t = owner_->nodes_[t].l;
}
}
return ans;
}
// ------------------------------------------------------------
// upper_bound
//
// ranges::upper_bound 相当。
// ------------------------------------------------------------
template <
class T,
class Comp = std::ranges::less,
class Proj = std::identity
>
int upper_bound(
const T& value,
Comp comp = {},
Proj proj = {}
) {
check_owner();
int t = root_;
int base = 0;
int ans = size();
while (t != nil) {
owner_->push(t);
int ls =
owner_->node_size(
owner_->nodes_[t].l
);
int idx =
base + ls;
if (
!std::invoke(
comp,
value,
std::invoke(
proj,
owner_->nodes_[t].val
)
)
) {
base = idx + 1;
t = owner_->nodes_[t].r;
} else {
ans = idx;
t = owner_->nodes_[t].l;
}
}
return ans;
}
};
private:
int max_nodes_;
std::vector<Node> nodes_;
std::vector<int> free_;
uint64_t rng_state_;
// ------------------------------------------------------------
// RNG
// ------------------------------------------------------------
static uint64_t default_seed() {
return
uint64_t(
std::chrono::steady_clock::now()
.time_since_epoch()
.count()
)
^
uint64_t(
reinterpret_cast<uintptr_t>(
&default_seed
)
);
}
uint64_t rng() {
uint64_t z =
(
rng_state_
+= 0x9e3779b97f4a7c15ULL
);
z =
(z ^ (z >> 30))
* 0xbf58476d1ce4e5b9ULL;
z =
(z ^ (z >> 27))
* 0x94d049bb133111ebULL;
return
z ^ (z >> 31);
}
// ------------------------------------------------------------
// basic node utilities
// ------------------------------------------------------------
int node_size(int t) const {
return t == nil
? 0
: nodes_[t].sz;
}
bool higher(
int a,
int b
) const {
if (
nodes_[a].pri
!= nodes_[b].pri
) {
return
nodes_[a].pri
> nodes_[b].pri;
}
// priority collision を完全に処理
return a > b;
}
int new_node(S x) {
int v;
if (!free_.empty()) {
v = free_.back();
free_.pop_back();
nodes_[v] =
Node(
std::move(x),
rng()
);
} else {
assert(
static_cast<int>(
nodes_.size()
)
< max_nodes_
&&
"implicit_treap node pool exhausted"
);
v =
static_cast<int>(
nodes_.size()
);
nodes_.emplace_back(
std::move(x),
rng()
);
}
return v;
}
void release_node(int v) {
assert(v != nil);
free_.push_back(v);
}
// 部分木全体を freelist に返す。
// lazy を push する必要はない。
void release_tree(int root) {
if (root == nil) {
return;
}
std::vector<int> st{
root
};
while (!st.empty()) {
int v = st.back();
st.pop_back();
if (nodes_[v].l != nil) {
st.push_back(
nodes_[v].l
);
}
if (nodes_[v].r != nil) {
st.push_back(
nodes_[v].r
);
}
free_.push_back(v);
}
}
// ------------------------------------------------------------
// aggregate
// ------------------------------------------------------------
S aggregate(int t) const {
return t == nil
? e()
: nodes_[t].agg.prod;
}
void pull(int t) {
Node& n =
nodes_[t];
n.sz =
node_size(n.l)
+ 1
+ node_size(n.r);
if constexpr (has_monoid) {
n.agg.prod =
op(
op(
aggregate(n.l),
n.val
),
aggregate(n.r)
);
}
}
// ------------------------------------------------------------
// lazy
//
// composition(f, g) = f ∘ g
// ACL と同じ順序。
// ------------------------------------------------------------
void apply_all(
int t,
const F& f
) {
if (t == nil) {
return;
}
if constexpr (has_lazy) {
Node& n =
nodes_[t];
n.val =
mapping(
f,
n.val
);
n.agg.prod =
mapping(
f,
n.agg.prod
);
if (n.lazy.pending) {
n.lazy.tag =
composition(
f,
n.lazy.tag
);
} else {
n.lazy.tag = f;
n.lazy.pending = true;
}
}
}
// ------------------------------------------------------------
// push
// ------------------------------------------------------------
void push(int t) {
if constexpr (has_lazy) {
if (t == nil) {
return;
}
Node& n =
nodes_[t];
if (n.lazy.pending) {
F f =
n.lazy.tag;
apply_all(
n.l,
f
);
apply_all(
n.r,
f
);
n.lazy.pending = false;
n.lazy.tag = id();
}
}
}
// ------------------------------------------------------------
// split / merge core
// ------------------------------------------------------------
std::pair<int, int>
split_root(
int t,
int k
) {
if (t == nil) {
return {
nil,
nil
};
}
assert(
0 <= k &&
k <= node_size(t)
);
push(t);
int ls =
node_size(
nodes_[t].l
);
if (k <= ls) {
auto [a, b] =
split_root(
nodes_[t].l,
k
);
nodes_[t].l = b;
pull(t);
return {
a,
t
};
} else {
auto [a, b] =
split_root(
nodes_[t].r,
k - ls - 1
);
nodes_[t].r = a;
pull(t);
return {
t,
b
};
}
}
int merge_root(
int a,
int b
) {
if (a == nil) {
return b;
}
if (b == nil) {
return a;
}
if (higher(a, b)) {
push(a);
nodes_[a].r =
merge_root(
nodes_[a].r,
b
);
pull(a);
return a;
} else {
push(b);
nodes_[b].l =
merge_root(
a,
nodes_[b].l
);
pull(b);
return b;
}
}
// ------------------------------------------------------------
// set / get
// ------------------------------------------------------------
void set_impl(
int t,
int p,
S x
) {
push(t);
int ls =
node_size(
nodes_[t].l
);
if (p < ls) {
set_impl(
nodes_[t].l,
p,
std::move(x)
);
} else if (p == ls) {
nodes_[t].val =
std::move(x);
} else {
set_impl(
nodes_[t].r,
p - ls - 1,
std::move(x)
);
}
pull(t);
}
S get_impl(
int t,
int p
) {
while (true) {
push(t);
int ls =
node_size(
nodes_[t].l
);
if (p < ls) {
t =
nodes_[t].l;
} else if (p == ls) {
return
nodes_[t].val;
} else {
p -= ls + 1;
t =
nodes_[t].r;
}
}
}
// ------------------------------------------------------------
// to_vector
//
// subtree t の [l, r) を inorder で res に追加する。
// ------------------------------------------------------------
void to_vector_impl(
int t,
int l,
int r,
std::vector<S>& res
) {
if (
t == nil ||
l == r
) {
return;
}
assert(
0 <= l &&
l <= r &&
r <= node_size(t)
);
push(t);
int ls =
node_size(
nodes_[t].l
);
// 左部分木との共通部分
if (l < ls) {
to_vector_impl(
nodes_[t].l,
l,
std::min(r, ls),
res
);
}
// 自分自身
if (
l <= ls &&
ls < r
) {
res.push_back(
nodes_[t].val
);
}
// 右部分木との共通部分
if (r > ls + 1) {
int nl =
std::max(
0,
l - ls - 1
);
int nr =
r - ls - 1;
to_vector_impl(
nodes_[t].r,
nl,
nr,
res
);
}
}
// ------------------------------------------------------------
// prod
// ------------------------------------------------------------
S prod_impl(
int t,
int l,
int r
) {
if (l == r) {
return e();
}
if (
l == 0 &&
r == node_size(t)
) {
return
nodes_[t].agg.prod;
}
push(t);
int ls =
node_size(
nodes_[t].l
);
S res = e();
if (l < ls) {
res =
op(
res,
prod_impl(
nodes_[t].l,
l,
std::min(r, ls)
)
);
}
if (
l <= ls &&
ls < r
) {
res =
op(
res,
nodes_[t].val
);
}
if (r > ls + 1) {
int nl =
std::max(
0,
l - ls - 1
);
int nr =
r - ls - 1;
res =
op(
res,
prod_impl(
nodes_[t].r,
nl,
nr
)
);
}
return res;
}
// ------------------------------------------------------------
// point apply
// ------------------------------------------------------------
void apply_point_impl(
int t,
int p,
const F& f
) {
push(t);
int ls =
node_size(
nodes_[t].l
);
if (p < ls) {
apply_point_impl(
nodes_[t].l,
p,
f
);
} else if (p == ls) {
// subtree 全体ではなく
// この要素だけに mapping
nodes_[t].val =
mapping(
f,
nodes_[t].val
);
} else {
apply_point_impl(
nodes_[t].r,
p - ls - 1,
f
);
}
pull(t);
}
// ------------------------------------------------------------
// range apply
// ------------------------------------------------------------
void apply_range_impl(
int t,
int l,
int r,
const F& f
) {
if (
l == r ||
t == nil
) {
return;
}
if (
l == 0 &&
r == node_size(t)
) {
apply_all(
t,
f
);
return;
}
push(t);
int ls =
node_size(
nodes_[t].l
);
if (l < ls) {
apply_range_impl(
nodes_[t].l,
l,
std::min(r, ls),
f
);
}
if (
l <= ls &&
ls < r
) {
nodes_[t].val =
mapping(
f,
nodes_[t].val
);
}
if (r > ls + 1) {
int nl =
std::max(
0,
l - ls - 1
);
int nr =
r - ls - 1;
apply_range_impl(
nodes_[t].r,
nl,
nr,
f
);
}
pull(t);
}
// ------------------------------------------------------------
// max_right
// ------------------------------------------------------------
template <class G>
int max_right_impl(
int t,
int l,
S& sm,
G& g
) {
int n =
node_size(t);
if (
t == nil ||
l == n
) {
return n;
}
// subtree 全体を一発で取れる場合
if (l == 0) {
S cand =
op(
sm,
nodes_[t].agg.prod
);
if (
std::invoke(
g,
cand
)
) {
sm =
std::move(cand);
return n;
}
}
push(t);
int ls =
node_size(
nodes_[t].l
);
if (l < ls) {
int x =
max_right_impl(
nodes_[t].l,
l,
sm,
g
);
if (x < ls) {
return x;
}
S cand =
op(
sm,
nodes_[t].val
);
if (
!std::invoke(
g,
cand
)
) {
return ls;
}
sm =
std::move(cand);
int y =
max_right_impl(
nodes_[t].r,
0,
sm,
g
);
return
ls + 1 + y;
}
if (l == ls) {
S cand =
op(
sm,
nodes_[t].val
);
if (
!std::invoke(
g,
cand
)
) {
return ls;
}
sm =
std::move(cand);
int y =
max_right_impl(
nodes_[t].r,
0,
sm,
g
);
return
ls + 1 + y;
}
int y =
max_right_impl(
nodes_[t].r,
l - ls - 1,
sm,
g
);
return
ls + 1 + y;
}
// ------------------------------------------------------------
// min_left
// ------------------------------------------------------------
template <class G>
int min_left_impl(
int t,
int r,
S& sm,
G& g
) {
int n =
node_size(t);
if (
t == nil ||
r == 0
) {
return 0;
}
// subtree 全体
if (r == n) {
S cand =
op(
nodes_[t].agg.prod,
sm
);
if (
std::invoke(
g,
cand
)
) {
sm =
std::move(cand);
return 0;
}
}
push(t);
int ls =
node_size(
nodes_[t].l
);
if (r > ls + 1) {
int x =
min_left_impl(
nodes_[t].r,
r - ls - 1,
sm,
g
);
if (x > 0) {
return
ls + 1 + x;
}
S cand =
op(
nodes_[t].val,
sm
);
if (
!std::invoke(
g,
cand
)
) {
return
ls + 1;
}
sm =
std::move(cand);
return
min_left_impl(
nodes_[t].l,
ls,
sm,
g
);
}
if (r == ls + 1) {
S cand =
op(
nodes_[t].val,
sm
);
if (
!std::invoke(
g,
cand
)
) {
return
ls + 1;
}
sm =
std::move(cand);
return
min_left_impl(
nodes_[t].l,
ls,
sm,
g
);
}
return
min_left_impl(
nodes_[t].l,
r,
sm,
g
);
}
// ------------------------------------------------------------
// O(n) build
//
// priority から Cartesian Tree を構築。
// ------------------------------------------------------------
int build_from_vector(
std::vector<S> values
) {
if (values.empty()) {
return nil;
}
int active =
static_cast<int>(
nodes_.size()
)
-
static_cast<int>(
free_.size()
);
assert(
static_cast<int>(
values.size()
)
<= max_nodes_ - active
&&
"implicit_treap node pool exhausted"
);
std::vector<int> ids;
ids.reserve(
values.size()
);
for (auto& x : values) {
ids.push_back(
new_node(
std::move(x)
)
);
}
std::vector<int> st;
st.reserve(
ids.size()
);
for (int v : ids) {
int last = nil;
while (
!st.empty() &&
higher(
v,
st.back()
)
) {
last =
st.back();
st.pop_back();
}
nodes_[v].l =
last;
if (!st.empty()) {
nodes_[st.back()].r =
v;
}
st.push_back(v);
}
int root =
st.front();
// post-order pull
std::vector<int> order;
order.reserve(
ids.size()
);
std::vector<int> dfs{
root
};
while (!dfs.empty()) {
int v =
dfs.back();
dfs.pop_back();
order.push_back(v);
if (nodes_[v].l != nil) {
dfs.push_back(
nodes_[v].l
);
}
if (nodes_[v].r != nil) {
dfs.push_back(
nodes_[v].r
);
}
}
for (
auto it = order.rbegin();
it != order.rend();
++it
) {
pull(*it);
}
return root;
}
public:
// ------------------------------------------------------------
// pool constructor
// ------------------------------------------------------------
explicit implicit_treap(
int max_nodes,
uint64_t seed = default_seed()
)
: max_nodes_(max_nodes),
rng_state_(seed) {
assert(
max_nodes >= 0
);
nodes_.reserve(
max_nodes_
);
free_.reserve(
max_nodes_
);
}
implicit_treap(
const implicit_treap&
) = delete;
implicit_treap&
operator=(
const implicit_treap&
) = delete;
// ------------------------------------------------------------
// sequence construction
// ------------------------------------------------------------
sequence make_sequence() {
return
sequence(
this,
nil
);
}
sequence make_sequence(
std::vector<S> values
) {
return
sequence(
this,
build_from_vector(
std::move(values)
)
);
}
sequence make_sequence(
std::initializer_list<S> values
) {
return
make_sequence(
std::vector<S>(
values
)
);
}
// 短い alias
sequence make() {
return
make_sequence();
}
sequence make(
std::vector<S> values
) {
return
make_sequence(
std::move(values)
);
}
sequence make(
std::initializer_list<S> values
) {
return
make_sequence(values);
}
// ------------------------------------------------------------
// pool-level merge
//
// a,b を両方 consume して新しい sequence を返す。
// ------------------------------------------------------------
sequence merge(
sequence&& a,
sequence&& b
) {
assert(
&a != &b
);
a.check_owner();
b.check_owner();
assert(
a.owner_ == this &&
b.owner_ == this &&
"cannot merge sequences from different pools"
);
int ar =
a.root_;
int br =
b.root_;
a.root_ = nil;
b.root_ = nil;
a.owner_ = nullptr;
b.owner_ = nullptr;
return
sequence(
this,
merge_root(
ar,
br
)
);
}
// ------------------------------------------------------------
// pool-level split
// ------------------------------------------------------------
std::pair<sequence, sequence>
split(
sequence&& s,
int k
) {
s.check_owner();
assert(
s.owner_ == this
);
return
s.split(k);
}
// ------------------------------------------------------------
// pool information
// ------------------------------------------------------------
int capacity() const {
return max_nodes_;
}
int allocated_nodes() const {
return
static_cast<int>(
nodes_.size()
)
-
static_cast<int>(
free_.size()
);
}
};
// implicit_treap<S> pool(n);
// auto t=pool.make(vec);