Generic Segment Tree Beats!
(ds/segtree/segtree_beats.hpp)

View this file on GitHub
Last update: 2026-08-12 01:20:42+09:00
Include: #include "ds/segtree/segtree_beats.hpp"

Overview

m1une::ds::SegtreeBeats<ActedMonoid> is a generic lazy segment tree for actions that cannot always be applied to an aggregated node. When can_apply(f, x) is false, the tree pushes any older lazy operator, descends to the children, applies f there, and rebuilds the node.

This is the library’s generic meaning of Segment Tree Beats. It is not tied to chmin or chmax. For the ready-made numeric structure supporting range chmin, range chmax, range addition, and sum/min/max queries, use ChminChmaxAddSegtree<T>.

Use LazySegtree<ActedMonoid> when every valid action always maps an aggregate directly. Its simpler contract gives the usual $O(\log N)$ update bound.

Beats acted monoid

ActedMonoid must satisfy m1une::beats_acted_monoid::IsBeatsActedMonoid and provide:

using value_type = T;
using operator_type = F;

static T id();
static T op(const T& lhs, const T& rhs);

static F op_id();
static F op_comp(const F& f, const F& g);

static T mapping(const F& f, const T& x);
static bool can_apply(const F& f, const T& x);

op_comp(f, g) represents applying g first and then f.

The exact applicability contract is:

If can_apply(f, x) is true, mapping(f, x) must return the correct updated aggregate without inspecting children.
If it is false, mapping is not called and f is not composed into that node’s lazy tag.
A failed internal application pushes the node’s existing lazy tag first, recursively applies f to both children, and rebuilds the aggregate with op.
Pushing a stored operator uses the same fallible procedure. It may itself descend multiple levels before propagation finishes.
Every valid operator must be applicable at every real leaf. Reaching a real leaf for which can_apply is false triggers an assertion.
op_id() must always be applicable and mapping(op_id(), x) must equal x.

Padded leaves are excluded by the data structure and do not impose an application-specific can_apply requirement.

Optional index-aware operations

The following overloads are detected automatically:

static T mapping(const F& f, const T& x, long long ordinal);
static bool can_apply(const F& f, const T& x, long long ordinal);
static F op_shift(const F& f, long long offset);

An operator passed to apply(l, r, f) is relative to index l. A covered node starting at p receives op_shift(f, p - l). On descent, the left child keeps offset zero relative to its parent and the right child receives the operator shifted by the left child’s interval length. The index-aware mapping and applicability overloads receive the ordinal relative to the already shifted operator; the current implementation calls them with zero at a node.

Construction from std::vector<U> uses ActedMonoid::make(value) when available, then ActedMonoid::make(value, index), then conversion to value_type.

beats_acted_monoid/wrapper.hpp provides m1une::beats_acted_monoid::Wrapper for assembling the required functions from constexpr lambdas or function objects. It can also forward optional make, index-aware mapping/applicability, and shifting functions.

Public interface

All indices are zero-based and all ranges are half-open.

Method	Description	Complexity
`SegtreeBeats()`	Constructs an empty tree.	$O(1)$
`SegtreeBeats(int n)`	Constructs `n` identity values.	$O(N)$
`SegtreeBeats(const std::vector<T>& v)`	Copies and builds from acted-monoid values.	$O(N)$
`SegtreeBeats(std::vector<T>&& v)`	Moves and builds from acted-monoid values.	$O(N)$
`SegtreeBeats(const std::vector<U>& v)`	Converts with `make` or conversion and builds.	$O(N)$
`int size() const`	Returns the number of real elements.	$O(1)$
`bool empty() const`	Returns whether there are no elements.	$O(1)$
`void set(int p, T x)`	Assigns element `p`.	$O(\log N + D)$
`T get(int p)`	Returns element `p`.	$O(\log N + D)$
`T operator[](int p)`	Returns element `p`.	$O(\log N + D)$
`T prod(int l, int r)`	Returns the monoid product of `[l, r)`.	$O(\log N + D)$
`T all_prod() const`	Returns the whole-array product.	$O(1)$
`void apply(int p, F f)`	Applies `f` to element `p`.	$O(\log N + D)$
`void apply(int l, int r, F f)`	Applies `f` to `[l, r)`.	$O(\log N + D)$
`std::vector<T> to_vector()`	Materializes every element.	$O(N + D)$
`std::vector<T> to_vector(int l, int r)`	Materializes `[l, r)`.	$O((r-l)+\log N+D)$
`int max_right(int l, Predicate g)`	Finds the largest `r` for which `g(prod(l, r))` is true.	$O(\log N + D)$
`int min_left(int r, Predicate g)`	Finds the smallest `l` for which `g(prod(l, r))` is true.	$O(\log N + D)$

Here, $D$ is the number of additional nodes visited because direct application of a new or stored operator fails. Empty products return id(). Boundary-search predicates must accept id().

A generic update is therefore $O(\log N + D)$, not automatically amortized $O(\log N)$. A stronger bound must be proved for the particular acted monoid, usually with a potential argument or a bound on exceptional state transitions. Because queries may push stored operators, their $D$ can also be nonzero.

Non-chmin/chmax example

Consider reactors with a pressure threshold. A value stores the minimum remaining pressure before any active reactor vents, the total number of vents, and the number and length of terminal reactors. An update stores both the added pressure and one operation count.

The update is directly applicable when all reactors are terminal, no active reactor reaches its threshold, or the node is a leaf. Otherwise can_apply(update, node) returns false. The generic tree descends only through segments containing exceptional transitions; a leaf that vents can halve its threshold and reset its pressure. This is a Beats action even though it uses no chmin or chmax operation.

Depends on

Verified with

Code

#ifndef M1UNE_DS_SEGTREE_BEATS_HPP
#define M1UNE_DS_SEGTREE_BEATS_HPP 1

#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

#include "../../beats_acted_monoid/concept.hpp"
#include "../../math/bit_ceil.hpp"

namespace m1une {
namespace ds {

// Generic Segment Tree Beats for actions that may require recursive descent.
template <m1une::beats_acted_monoid::IsBeatsActedMonoid ActedMonoid>
struct SegtreeBeats {
    using value_type = typename ActedMonoid::value_type;
    using operator_type = typename ActedMonoid::operator_type;
    using T = value_type;
    using F = operator_type;

   private:
    int _n = 0;
    int _size = 1;
    std::vector<T> _data;
    std::vector<F> _lazy;

    static T mapping_at(const F& f, const T& value, long long ordinal) {
        if constexpr (requires(F g, T x, long long i) {
            ActedMonoid::mapping(g, x, i);
        }) {
            return ActedMonoid::mapping(f, value, ordinal);
        } else {
            return ActedMonoid::mapping(f, value);
        }
    }

    static bool can_apply_at(const F& f, const T& value, long long ordinal) {
        if constexpr (requires(F g, T x, long long i) {
            ActedMonoid::can_apply(g, x, i);
        }) {
            return ActedMonoid::can_apply(f, value, ordinal);
        } else {
            return ActedMonoid::can_apply(f, value);
        }
    }

    static F shift_operator(const F& f, long long ordinal) {
        if constexpr (requires(F g, long long i) {
            ActedMonoid::op_shift(g, i);
        }) {
            return ActedMonoid::op_shift(f, ordinal);
        } else {
            return f;
        }
    }

    void initialize(std::vector<T>&& values) {
        _n = int(values.size());
        _size = int(m1une::math::bit_ceil((unsigned int)_n));
        _data.assign(2 * _size, ActedMonoid::id());
        _lazy.assign(_size, ActedMonoid::op_id());
        for (int i = 0; i < _n; ++i) {
            _data[_size + i] = std::move(values[i]);
        }
        for (int k = _size - 1; k >= 1; --k) update(k);
    }

    void update(int node) {
        _data[node] = ActedMonoid::op(
            _data[node * 2],
            _data[node * 2 + 1]
        );
    }

    void all_apply(int node, int left, int right, const F& f) {
        if (_n <= left) return;
        if (can_apply_at(f, _data[node], 0)) {
            _data[node] = mapping_at(f, _data[node], 0);
            if (node < _size) {
                _lazy[node] = ActedMonoid::op_comp(f, _lazy[node]);
            }
            return;
        }

        assert(right - left > 1);
        push(node, left, right);
        int middle = left + (right - left) / 2;
        all_apply(node * 2, left, middle, f);
        all_apply(
            node * 2 + 1,
            middle,
            right,
            shift_operator(f, middle - left)
        );
        update(node);
    }

    void push(int node, int left, int right) {
        assert(right - left > 1);
        int middle = left + (right - left) / 2;
        F f = _lazy[node];
        _lazy[node] = ActedMonoid::op_id();
        all_apply(node * 2, left, middle, f);
        all_apply(
            node * 2 + 1,
            middle,
            right,
            shift_operator(f, middle - left)
        );
    }

    void set_impl(
        int node,
        int left,
        int right,
        int index,
        T value
    ) {
        if (right - left == 1) {
            _data[node] = std::move(value);
            return;
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        if (index < middle) {
            set_impl(node * 2, left, middle, index, std::move(value));
        } else {
            set_impl(
                node * 2 + 1,
                middle,
                right,
                index,
                std::move(value)
            );
        }
        update(node);
    }

    T get_impl(int node, int left, int right, int index) {
        if (right - left == 1) return _data[node];
        push(node, left, right);
        int middle = left + (right - left) / 2;
        if (index < middle) {
            return get_impl(node * 2, left, middle, index);
        }
        return get_impl(node * 2 + 1, middle, right, index);
    }

    T prod_impl(
        int node,
        int left,
        int right,
        int query_left,
        int query_right
    ) {
        if (
            query_right <= left || right <= query_left || _n <= left
        ) {
            return ActedMonoid::id();
        }
        if (query_left <= left && right <= query_right) {
            return _data[node];
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        return ActedMonoid::op(
            prod_impl(
                node * 2,
                left,
                middle,
                query_left,
                query_right
            ),
            prod_impl(
                node * 2 + 1,
                middle,
                right,
                query_left,
                query_right
            )
        );
    }

    void apply_impl(
        int node,
        int left,
        int right,
        int query_left,
        int query_right,
        int base_left,
        const F& f
    ) {
        if (
            query_right <= left || right <= query_left || _n <= left
        ) {
            return;
        }
        if (query_left <= left && right <= query_right) {
            all_apply(
                node,
                left,
                right,
                shift_operator(f, left - base_left)
            );
            return;
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        apply_impl(
            node * 2,
            left,
            middle,
            query_left,
            query_right,
            base_left,
            f
        );
        apply_impl(
            node * 2 + 1,
            middle,
            right,
            query_left,
            query_right,
            base_left,
            f
        );
        update(node);
    }

    void collect_impl(
        int node,
        int left,
        int right,
        int query_left,
        int query_right,
        std::vector<T>& result
    ) {
        if (
            query_right <= left || right <= query_left || _n <= left
        ) {
            return;
        }
        if (right - left == 1) {
            result.push_back(_data[node]);
            return;
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        collect_impl(
            node * 2,
            left,
            middle,
            query_left,
            query_right,
            result
        );
        collect_impl(
            node * 2 + 1,
            middle,
            right,
            query_left,
            query_right,
            result
        );
    }

    template <class Predicate>
    bool max_right_impl(
        int node,
        int left,
        int right,
        int query_left,
        Predicate& predicate,
        T& product,
        int& answer
    ) {
        if (right <= query_left || _n <= left) return true;
        if (query_left <= left) {
            T next = ActedMonoid::op(product, _data[node]);
            if (predicate(next)) {
                product = std::move(next);
                return true;
            }
            if (right - left == 1) {
                answer = left;
                return false;
            }
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        if (!max_right_impl(
                node * 2,
                left,
                middle,
                query_left,
                predicate,
                product,
                answer
            )) {
            return false;
        }
        return max_right_impl(
            node * 2 + 1,
            middle,
            right,
            query_left,
            predicate,
            product,
            answer
        );
    }

    template <class Predicate>
    bool min_left_impl(
        int node,
        int left,
        int right,
        int query_right,
        Predicate& predicate,
        T& product,
        int& answer
    ) {
        if (query_right <= left || _n <= left) return true;
        if (right <= query_right) {
            T next = ActedMonoid::op(_data[node], product);
            if (predicate(next)) {
                product = std::move(next);
                return true;
            }
            if (right - left == 1) {
                answer = right;
                return false;
            }
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        if (!min_left_impl(
                node * 2 + 1,
                middle,
                right,
                query_right,
                predicate,
                product,
                answer
            )) {
            return false;
        }
        return min_left_impl(
            node * 2,
            left,
            middle,
            query_right,
            predicate,
            product,
            answer
        );
    }

   public:
    SegtreeBeats() {
        initialize({});
    }

    explicit SegtreeBeats(int n) {
        assert(0 <= n);
        initialize(std::vector<T>(n, ActedMonoid::id()));
    }

    explicit SegtreeBeats(const std::vector<T>& values) {
        initialize(std::vector<T>(values));
    }

    explicit SegtreeBeats(std::vector<T>&& values) {
        initialize(std::move(values));
    }

    template <typename U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit SegtreeBeats(const std::vector<U>& values) {
        std::vector<T> converted;
        converted.reserve(values.size());
        for (int i = 0; i < int(values.size()); ++i) {
            if constexpr (requires(U x) { ActedMonoid::make(x); }) {
                converted.push_back(ActedMonoid::make(values[i]));
            } else if constexpr (requires(U x, int index) {
                ActedMonoid::make(x, index);
            }) {
                converted.push_back(ActedMonoid::make(values[i], i));
            } else {
                converted.push_back(static_cast<T>(values[i]));
            }
        }
        initialize(std::move(converted));
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    void set(int index, T value) {
        assert(0 <= index && index < _n);
        set_impl(1, 0, _size, index, std::move(value));
    }

    T get(int index) {
        assert(0 <= index && index < _n);
        return get_impl(1, 0, _size, index);
    }

    T operator[](int index) {
        return get(index);
    }

    T prod(int left, int right) {
        assert(0 <= left && left <= right && right <= _n);
        if (left == right) return ActedMonoid::id();
        return prod_impl(1, 0, _size, left, right);
    }

    T all_prod() const {
        return _data[1];
    }

    void apply(int index, F f) {
        assert(0 <= index && index < _n);
        apply_impl(1, 0, _size, index, index + 1, index, f);
    }

    void apply(int left, int right, F f) {
        assert(0 <= left && left <= right && right <= _n);
        if (left == right) return;
        apply_impl(1, 0, _size, left, right, left, f);
    }

    std::vector<T> to_vector() {
        return to_vector(0, _n);
    }

    std::vector<T> to_vector(int left, int right) {
        assert(0 <= left && left <= right && right <= _n);
        std::vector<T> result;
        result.reserve(right - left);
        collect_impl(1, 0, _size, left, right, result);
        return result;
    }

    template <class Predicate>
    int max_right(int left, Predicate predicate) {
        assert(0 <= left && left <= _n);
        assert(predicate(ActedMonoid::id()));
        if (left == _n) return _n;
        T product = ActedMonoid::id();
        int answer = _n;
        max_right_impl(
            1,
            0,
            _size,
            left,
            predicate,
            product,
            answer
        );
        return answer;
    }

    template <class Predicate>
    int min_left(int right, Predicate predicate) {
        assert(0 <= right && right <= _n);
        assert(predicate(ActedMonoid::id()));
        if (right == 0) return 0;
        T product = ActedMonoid::id();
        int answer = 0;
        min_left_impl(
            1,
            0,
            _size,
            right,
            predicate,
            product,
            answer
        );
        return answer;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_SEGTREE_BEATS_HPP

#line 1 "ds/segtree/segtree_beats.hpp"



#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

#line 1 "beats_acted_monoid/concept.hpp"



#line 5 "beats_acted_monoid/concept.hpp"

#line 1 "acted_monoid/concept.hpp"



#line 5 "acted_monoid/concept.hpp"

namespace m1une {
namespace acted_monoid {

// Concept defining the requirements for an Acted Monoid.
template <typename AM>
concept IsActedMonoid = requires(typename AM::value_type a, typename AM::value_type b, typename AM::operator_type f,
                                 typename AM::operator_type g) {
    // 1. Value Monoid
    typename AM::value_type;
    { AM::id() } -> std::same_as<typename AM::value_type>;
    { AM::op(a, b) } -> std::same_as<typename AM::value_type>;

    // 2. Operator Monoid
    typename AM::operator_type;
    { AM::op_id() } -> std::same_as<typename AM::operator_type>;
    { AM::op_comp(f, g) } -> std::same_as<typename AM::operator_type>;  // Composition order: f(g(x))

    // 3. Mapping: Operator x Value -> Value
    { AM::mapping(f, a) } -> std::same_as<typename AM::value_type>;
};

// Concept for acted monoids whose value monoid is a commutative group.
// The value operation must obey commutativity and inverse laws.
template <typename AM>
concept IsCommutativeActedGroup = IsActedMonoid<AM> && requires(typename AM::value_type a) {
    { AM::inv(a) } -> std::same_as<typename AM::value_type>;
};

}  // namespace acted_monoid
}  // namespace m1une


#line 7 "beats_acted_monoid/concept.hpp"

namespace m1une {
namespace beats_acted_monoid {

// An acted monoid whose action may require descent before it can be applied.
template <typename AM>
concept IsBeatsActedMonoid = m1une::acted_monoid::IsActedMonoid<AM> &&
    requires(typename AM::value_type x, typename AM::operator_type f) {
        { AM::can_apply(f, x) } -> std::same_as<bool>;
    };

}  // namespace beats_acted_monoid
}  // namespace m1une


#line 1 "math/bit_ceil.hpp"



namespace m1une {
namespace math {

template <typename T>
constexpr T bit_ceil(T n) {
    if (n <= 1) return 1;
    T x = 1;
    while (x < n) x <<= 1;
    return x;
}

}  // namespace math
}  // namespace m1une


#line 11 "ds/segtree/segtree_beats.hpp"

namespace m1une {
namespace ds {

// Generic Segment Tree Beats for actions that may require recursive descent.
template <m1une::beats_acted_monoid::IsBeatsActedMonoid ActedMonoid>
struct SegtreeBeats {
    using value_type = typename ActedMonoid::value_type;
    using operator_type = typename ActedMonoid::operator_type;
    using T = value_type;
    using F = operator_type;

   private:
    int _n = 0;
    int _size = 1;
    std::vector<T> _data;
    std::vector<F> _lazy;

    static T mapping_at(const F& f, const T& value, long long ordinal) {
        if constexpr (requires(F g, T x, long long i) {
            ActedMonoid::mapping(g, x, i);
        }) {
            return ActedMonoid::mapping(f, value, ordinal);
        } else {
            return ActedMonoid::mapping(f, value);
        }
    }

    static bool can_apply_at(const F& f, const T& value, long long ordinal) {
        if constexpr (requires(F g, T x, long long i) {
            ActedMonoid::can_apply(g, x, i);
        }) {
            return ActedMonoid::can_apply(f, value, ordinal);
        } else {
            return ActedMonoid::can_apply(f, value);
        }
    }

    static F shift_operator(const F& f, long long ordinal) {
        if constexpr (requires(F g, long long i) {
            ActedMonoid::op_shift(g, i);
        }) {
            return ActedMonoid::op_shift(f, ordinal);
        } else {
            return f;
        }
    }

    void initialize(std::vector<T>&& values) {
        _n = int(values.size());
        _size = int(m1une::math::bit_ceil((unsigned int)_n));
        _data.assign(2 * _size, ActedMonoid::id());
        _lazy.assign(_size, ActedMonoid::op_id());
        for (int i = 0; i < _n; ++i) {
            _data[_size + i] = std::move(values[i]);
        }
        for (int k = _size - 1; k >= 1; --k) update(k);
    }

    void update(int node) {
        _data[node] = ActedMonoid::op(
            _data[node * 2],
            _data[node * 2 + 1]
        );
    }

    void all_apply(int node, int left, int right, const F& f) {
        if (_n <= left) return;
        if (can_apply_at(f, _data[node], 0)) {
            _data[node] = mapping_at(f, _data[node], 0);
            if (node < _size) {
                _lazy[node] = ActedMonoid::op_comp(f, _lazy[node]);
            }
            return;
        }

        assert(right - left > 1);
        push(node, left, right);
        int middle = left + (right - left) / 2;
        all_apply(node * 2, left, middle, f);
        all_apply(
            node * 2 + 1,
            middle,
            right,
            shift_operator(f, middle - left)
        );
        update(node);
    }

    void push(int node, int left, int right) {
        assert(right - left > 1);
        int middle = left + (right - left) / 2;
        F f = _lazy[node];
        _lazy[node] = ActedMonoid::op_id();
        all_apply(node * 2, left, middle, f);
        all_apply(
            node * 2 + 1,
            middle,
            right,
            shift_operator(f, middle - left)
        );
    }

    void set_impl(
        int node,
        int left,
        int right,
        int index,
        T value
    ) {
        if (right - left == 1) {
            _data[node] = std::move(value);
            return;
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        if (index < middle) {
            set_impl(node * 2, left, middle, index, std::move(value));
        } else {
            set_impl(
                node * 2 + 1,
                middle,
                right,
                index,
                std::move(value)
            );
        }
        update(node);
    }

    T get_impl(int node, int left, int right, int index) {
        if (right - left == 1) return _data[node];
        push(node, left, right);
        int middle = left + (right - left) / 2;
        if (index < middle) {
            return get_impl(node * 2, left, middle, index);
        }
        return get_impl(node * 2 + 1, middle, right, index);
    }

    T prod_impl(
        int node,
        int left,
        int right,
        int query_left,
        int query_right
    ) {
        if (
            query_right <= left || right <= query_left || _n <= left
        ) {
            return ActedMonoid::id();
        }
        if (query_left <= left && right <= query_right) {
            return _data[node];
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        return ActedMonoid::op(
            prod_impl(
                node * 2,
                left,
                middle,
                query_left,
                query_right
            ),
            prod_impl(
                node * 2 + 1,
                middle,
                right,
                query_left,
                query_right
            )
        );
    }

    void apply_impl(
        int node,
        int left,
        int right,
        int query_left,
        int query_right,
        int base_left,
        const F& f
    ) {
        if (
            query_right <= left || right <= query_left || _n <= left
        ) {
            return;
        }
        if (query_left <= left && right <= query_right) {
            all_apply(
                node,
                left,
                right,
                shift_operator(f, left - base_left)
            );
            return;
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        apply_impl(
            node * 2,
            left,
            middle,
            query_left,
            query_right,
            base_left,
            f
        );
        apply_impl(
            node * 2 + 1,
            middle,
            right,
            query_left,
            query_right,
            base_left,
            f
        );
        update(node);
    }

    void collect_impl(
        int node,
        int left,
        int right,
        int query_left,
        int query_right,
        std::vector<T>& result
    ) {
        if (
            query_right <= left || right <= query_left || _n <= left
        ) {
            return;
        }
        if (right - left == 1) {
            result.push_back(_data[node]);
            return;
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        collect_impl(
            node * 2,
            left,
            middle,
            query_left,
            query_right,
            result
        );
        collect_impl(
            node * 2 + 1,
            middle,
            right,
            query_left,
            query_right,
            result
        );
    }

    template <class Predicate>
    bool max_right_impl(
        int node,
        int left,
        int right,
        int query_left,
        Predicate& predicate,
        T& product,
        int& answer
    ) {
        if (right <= query_left || _n <= left) return true;
        if (query_left <= left) {
            T next = ActedMonoid::op(product, _data[node]);
            if (predicate(next)) {
                product = std::move(next);
                return true;
            }
            if (right - left == 1) {
                answer = left;
                return false;
            }
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        if (!max_right_impl(
                node * 2,
                left,
                middle,
                query_left,
                predicate,
                product,
                answer
            )) {
            return false;
        }
        return max_right_impl(
            node * 2 + 1,
            middle,
            right,
            query_left,
            predicate,
            product,
            answer
        );
    }

    template <class Predicate>
    bool min_left_impl(
        int node,
        int left,
        int right,
        int query_right,
        Predicate& predicate,
        T& product,
        int& answer
    ) {
        if (query_right <= left || _n <= left) return true;
        if (right <= query_right) {
            T next = ActedMonoid::op(_data[node], product);
            if (predicate(next)) {
                product = std::move(next);
                return true;
            }
            if (right - left == 1) {
                answer = right;
                return false;
            }
        }
        push(node, left, right);
        int middle = left + (right - left) / 2;
        if (!min_left_impl(
                node * 2 + 1,
                middle,
                right,
                query_right,
                predicate,
                product,
                answer
            )) {
            return false;
        }
        return min_left_impl(
            node * 2,
            left,
            middle,
            query_right,
            predicate,
            product,
            answer
        );
    }

   public:
    SegtreeBeats() {
        initialize({});
    }

    explicit SegtreeBeats(int n) {
        assert(0 <= n);
        initialize(std::vector<T>(n, ActedMonoid::id()));
    }

    explicit SegtreeBeats(const std::vector<T>& values) {
        initialize(std::vector<T>(values));
    }

    explicit SegtreeBeats(std::vector<T>&& values) {
        initialize(std::move(values));
    }

    template <typename U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit SegtreeBeats(const std::vector<U>& values) {
        std::vector<T> converted;
        converted.reserve(values.size());
        for (int i = 0; i < int(values.size()); ++i) {
            if constexpr (requires(U x) { ActedMonoid::make(x); }) {
                converted.push_back(ActedMonoid::make(values[i]));
            } else if constexpr (requires(U x, int index) {
                ActedMonoid::make(x, index);
            }) {
                converted.push_back(ActedMonoid::make(values[i], i));
            } else {
                converted.push_back(static_cast<T>(values[i]));
            }
        }
        initialize(std::move(converted));
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    void set(int index, T value) {
        assert(0 <= index && index < _n);
        set_impl(1, 0, _size, index, std::move(value));
    }

    T get(int index) {
        assert(0 <= index && index < _n);
        return get_impl(1, 0, _size, index);
    }

    T operator[](int index) {
        return get(index);
    }

    T prod(int left, int right) {
        assert(0 <= left && left <= right && right <= _n);
        if (left == right) return ActedMonoid::id();
        return prod_impl(1, 0, _size, left, right);
    }

    T all_prod() const {
        return _data[1];
    }

    void apply(int index, F f) {
        assert(0 <= index && index < _n);
        apply_impl(1, 0, _size, index, index + 1, index, f);
    }

    void apply(int left, int right, F f) {
        assert(0 <= left && left <= right && right <= _n);
        if (left == right) return;
        apply_impl(1, 0, _size, left, right, left, f);
    }

    std::vector<T> to_vector() {
        return to_vector(0, _n);
    }

    std::vector<T> to_vector(int left, int right) {
        assert(0 <= left && left <= right && right <= _n);
        std::vector<T> result;
        result.reserve(right - left);
        collect_impl(1, 0, _size, left, right, result);
        return result;
    }

    template <class Predicate>
    int max_right(int left, Predicate predicate) {
        assert(0 <= left && left <= _n);
        assert(predicate(ActedMonoid::id()));
        if (left == _n) return _n;
        T product = ActedMonoid::id();
        int answer = _n;
        max_right_impl(
            1,
            0,
            _size,
            left,
            predicate,
            product,
            answer
        );
        return answer;
    }

    template <class Predicate>
    int min_left(int right, Predicate predicate) {
        assert(0 <= right && right <= _n);
        assert(predicate(ActedMonoid::id()));
        if (right == 0) return 0;
        T product = ActedMonoid::id();
        int answer = 0;
        min_left_impl(
            1,
            0,
            _size,
            right,
            predicate,
            product,
            answer
        );
        return answer;
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Generic Segment Tree Beats!
(ds/segtree/segtree_beats.hpp)

Overview

Beats acted monoid

Optional index-aware operations

Public interface

Non-chmin/chmax example

Depends on

Verified with

Code

Generic Segment Tree Beats! (ds/segtree/segtree_beats.hpp)

Overview

Beats acted monoid

Optional index-aware operations

Public interface

Non-chmin/chmax example

Depends on

Verified with

Code

Generic Segment Tree Beats!
(ds/segtree/segtree_beats.hpp)