Range Chmin/Chmax/Add Range Sum
(beats_acted_monoid/range_chmin_chmax_add_range_sum.hpp)

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

Overview

m1une::beats_acted_monoid::RangeChminChmaxAddRangeSum<T> is a Beats acted monoid for these range updates:

a[i] = min(a[i], upper)
a[i] = max(a[i], lower)
a[i] += add

It aggregates range sums and is intended for SegtreeBeats or PersistentSegtreeBeats. Each node stores the sum, minimum, second minimum, maximum, second maximum, their occurrence counts, and the segment length.

The lazy operator_type represents

f(x) = clamp(x + add, lower, upper);

Use make_chmin, make_chmax, and make_add instead of constructing that operator directly.

Template requirements

T must satisfy std::signed_integral and defaults to long long. All values, sums, differences, products by segment lengths, accumulated additions, and finite shifted bounds must remain representable by T.

value_type is RangeChminChmaxAddRangeSumNode<T> and has these public members:

T sum;
T maximum;
T second_maximum;
T minimum;
T second_minimum;
int maximum_count;
int minimum_count;
int length;

For a constant nonempty segment, second_maximum is std::numeric_limits<T>::lowest() and second_minimum is std::numeric_limits<T>::max().

Interface and complexity

Every acted-monoid operation below takes $O(1)$ time.

Member	Description	Complexity
`static value_type id()`	Returns the empty aggregate.	$O(1)$
`static value_type op(const value_type& x, const value_type& y)`	Concatenates two aggregates.	$O(1)$
`static operator_type op_id()`	Returns the identity update.	$O(1)$
`static operator_type op_comp(const operator_type& f, const operator_type& g)`	Returns $f \circ g$.	$O(1)$
`static bool can_apply(const operator_type& f, const value_type& x)`	Reports whether `mapping(f, x)` can update this node without descending.	$O(1)$
`static value_type mapping(const operator_type& f, const value_type& x)`	Applies an update after `can_apply` succeeds.	$O(1)$
`static value_type make(const T& value)`	Constructs a one-element aggregate.	$O(1)$
`static operator_type make_chmin(const T& upper)`	Constructs a range-`chmin` update.	$O(1)$
`static operator_type make_chmax(const T& lower)`	Constructs a range-`chmax` update.	$O(1)$
`static operator_type make_add(const T& add)`	Constructs a range-add update.	$O(1)$

can_apply succeeds when each clamp is a no-op, changes only the known extreme, or makes the segment constant. Otherwise the Beats tree descends. With SegtreeBeats, an operation takes $O(\log N+D)$, where $D$ is the number of extra nodes visited after failed applications.

Example

#include "beats_acted_monoid/range_chmin_chmax_add_range_sum.hpp"
#include "ds/segtree/segtree_beats.hpp"

#include <iostream>
#include <vector>

using AM =
    m1une::beats_acted_monoid::RangeChminChmaxAddRangeSum<long long>;

int main() {
    std::vector<long long> values = {8, 3, 6, 7};
    m1une::ds::SegtreeBeats<AM> seg(values);

    seg.apply(0, 4, AM::make_chmin(6));
    seg.apply(1, 3, AM::make_chmax(5));
    seg.apply(0, 2, AM::make_add(2));

    std::cout << seg.prod(0, 4).sum << '\n';
}

Verified with

Code

#ifndef M1UNE_BEATS_ACTED_MONOID_RANGE_CHMIN_CHMAX_ADD_RANGE_SUM_HPP
#define M1UNE_BEATS_ACTED_MONOID_RANGE_CHMIN_CHMAX_ADD_RANGE_SUM_HPP 1

#include <algorithm>
#include <cassert>
#include <concepts>
#include <limits>

namespace m1une {
namespace beats_acted_monoid {

template <std::signed_integral T>
struct RangeChminChmaxAddRangeSumNode {
    T sum;
    T maximum;
    T second_maximum;
    T minimum;
    T second_minimum;
    int maximum_count;
    int minimum_count;
    int length;
};

// Beats acted monoid for range chmin/chmax/add updates and range sum queries.
template <std::signed_integral T = long long>
struct RangeChminChmaxAddRangeSum {
    using value_type = RangeChminChmaxAddRangeSumNode<T>;

    // Represents f(x) = clamp(x + add, lower, upper).
    struct operator_type {
        T add;
        T lower;
        T upper;
    };

    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;
    static constexpr T negative_infinity = std::numeric_limits<T>::lowest();
    static constexpr T positive_infinity = std::numeric_limits<T>::max();

   private:
    static constexpr T shift_lower_bound(T bound, T add) {
        return bound == negative_infinity ? bound : bound + add;
    }

    static constexpr T shift_upper_bound(T bound, T add) {
        return bound == positive_infinity ? bound : bound + add;
    }

    static constexpr void apply_add(value_type& value, T add) {
        if (value.length == 0 || add == T(0)) return;
        value.sum += add * T(value.length);
        value.maximum += add;
        value.minimum += add;
        if (value.maximum_count != value.length) {
            value.second_maximum += add;
        }
        if (value.minimum_count != value.length) {
            value.second_minimum += add;
        }
    }

    static constexpr bool can_apply_chmin(
        const value_type& value,
        T upper
    ) {
        return value.maximum <= upper ||
            value.maximum_count == value.length ||
            value.second_maximum < upper;
    }

    static constexpr void apply_chmin(value_type& value, T upper) {
        if (value.maximum <= upper) return;
        assert(can_apply_chmin(value, upper));
        value.sum +=
            (upper - value.maximum) * T(value.maximum_count);
        if (value.minimum == value.maximum) {
            value.minimum = upper;
        } else if (value.second_minimum == value.maximum) {
            value.second_minimum = upper;
        }
        value.maximum = upper;
    }

    static constexpr bool can_apply_chmax(
        const value_type& value,
        T lower
    ) {
        return lower <= value.minimum ||
            value.minimum_count == value.length ||
            lower < value.second_minimum;
    }

    static constexpr void apply_chmax(value_type& value, T lower) {
        if (lower <= value.minimum) return;
        assert(can_apply_chmax(value, lower));
        value.sum +=
            (lower - value.minimum) * T(value.minimum_count);
        if (value.maximum == value.minimum) {
            value.maximum = lower;
        } else if (value.second_maximum == value.minimum) {
            value.second_maximum = lower;
        }
        value.minimum = lower;
    }

    static constexpr value_type constant_value(T value, int length) {
        return {
            value * T(length),
            value,
            negative_infinity,
            value,
            positive_infinity,
            length,
            length,
            length
        };
    }

   public:
    static constexpr value_type id() {
        return {
            T(0),
            negative_infinity,
            negative_infinity,
            positive_infinity,
            positive_infinity,
            0,
            0,
            0
        };
    }

    static constexpr value_type op(
        const value_type& left,
        const value_type& right
    ) {
        if (left.length == 0) return right;
        if (right.length == 0) return left;

        value_type result;
        result.sum = left.sum + right.sum;
        result.length = left.length + right.length;

        result.maximum = std::max(left.maximum, right.maximum);
        result.maximum_count = 0;
        result.second_maximum = negative_infinity;
        if (left.maximum == result.maximum) {
            result.maximum_count += left.maximum_count;
            result.second_maximum = std::max(
                result.second_maximum,
                left.second_maximum
            );
        } else {
            result.second_maximum = std::max(
                result.second_maximum,
                left.maximum
            );
        }
        if (right.maximum == result.maximum) {
            result.maximum_count += right.maximum_count;
            result.second_maximum = std::max(
                result.second_maximum,
                right.second_maximum
            );
        } else {
            result.second_maximum = std::max(
                result.second_maximum,
                right.maximum
            );
        }

        result.minimum = std::min(left.minimum, right.minimum);
        result.minimum_count = 0;
        result.second_minimum = positive_infinity;
        if (left.minimum == result.minimum) {
            result.minimum_count += left.minimum_count;
            result.second_minimum = std::min(
                result.second_minimum,
                left.second_minimum
            );
        } else {
            result.second_minimum = std::min(
                result.second_minimum,
                left.minimum
            );
        }
        if (right.minimum == result.minimum) {
            result.minimum_count += right.minimum_count;
            result.second_minimum = std::min(
                result.second_minimum,
                right.second_minimum
            );
        } else {
            result.second_minimum = std::min(
                result.second_minimum,
                right.minimum
            );
        }
        return result;
    }

    static constexpr operator_type op_id() {
        return {T(0), negative_infinity, positive_infinity};
    }

    // Returns f(g(x)).
    static constexpr operator_type op_comp(
        const operator_type& f,
        const operator_type& g
    ) {
        T lower = shift_lower_bound(g.lower, f.add);
        T upper = shift_upper_bound(g.upper, f.add);
        return {
            g.add + f.add,
            std::clamp(lower, f.lower, f.upper),
            std::clamp(upper, f.lower, f.upper)
        };
    }

    static constexpr bool can_apply(
        const operator_type& f,
        const value_type& value
    ) {
        if (value.length == 0 || f.lower == f.upper) return true;
        value_type mapped = value;
        apply_add(mapped, f.add);
        if (
            mapped.maximum <= f.lower ||
            f.upper <= mapped.minimum
        ) {
            return true;
        }
        if (!can_apply_chmax(mapped, f.lower)) return false;
        apply_chmax(mapped, f.lower);
        return can_apply_chmin(mapped, f.upper);
    }

    static constexpr value_type mapping(
        const operator_type& f,
        const value_type& value
    ) {
        assert(can_apply(f, value));
        if (value.length == 0) return value;
        if (f.lower == f.upper) {
            return constant_value(f.lower, value.length);
        }
        value_type result = value;
        apply_add(result, f.add);
        if (result.maximum <= f.lower) {
            return constant_value(f.lower, result.length);
        }
        if (f.upper <= result.minimum) {
            return constant_value(f.upper, result.length);
        }
        apply_chmax(result, f.lower);
        apply_chmin(result, f.upper);
        return result;
    }

    static constexpr value_type make(const T& value) {
        return constant_value(value, 1);
    }

    static constexpr operator_type make_chmin(const T& upper) {
        return {T(0), negative_infinity, upper};
    }

    static constexpr operator_type make_chmax(const T& lower) {
        return {T(0), lower, positive_infinity};
    }

    static constexpr operator_type make_add(const T& add) {
        return {add, negative_infinity, positive_infinity};
    }
};

}  // namespace beats_acted_monoid
}  // namespace m1une

#endif  // M1UNE_BEATS_ACTED_MONOID_RANGE_CHMIN_CHMAX_ADD_RANGE_SUM_HPP

#line 1 "beats_acted_monoid/range_chmin_chmax_add_range_sum.hpp"



#include <algorithm>
#include <cassert>
#include <concepts>
#include <limits>

namespace m1une {
namespace beats_acted_monoid {

template <std::signed_integral T>
struct RangeChminChmaxAddRangeSumNode {
    T sum;
    T maximum;
    T second_maximum;
    T minimum;
    T second_minimum;
    int maximum_count;
    int minimum_count;
    int length;
};

// Beats acted monoid for range chmin/chmax/add updates and range sum queries.
template <std::signed_integral T = long long>
struct RangeChminChmaxAddRangeSum {
    using value_type = RangeChminChmaxAddRangeSumNode<T>;

    // Represents f(x) = clamp(x + add, lower, upper).
    struct operator_type {
        T add;
        T lower;
        T upper;
    };

    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;
    static constexpr T negative_infinity = std::numeric_limits<T>::lowest();
    static constexpr T positive_infinity = std::numeric_limits<T>::max();

   private:
    static constexpr T shift_lower_bound(T bound, T add) {
        return bound == negative_infinity ? bound : bound + add;
    }

    static constexpr T shift_upper_bound(T bound, T add) {
        return bound == positive_infinity ? bound : bound + add;
    }

    static constexpr void apply_add(value_type& value, T add) {
        if (value.length == 0 || add == T(0)) return;
        value.sum += add * T(value.length);
        value.maximum += add;
        value.minimum += add;
        if (value.maximum_count != value.length) {
            value.second_maximum += add;
        }
        if (value.minimum_count != value.length) {
            value.second_minimum += add;
        }
    }

    static constexpr bool can_apply_chmin(
        const value_type& value,
        T upper
    ) {
        return value.maximum <= upper ||
            value.maximum_count == value.length ||
            value.second_maximum < upper;
    }

    static constexpr void apply_chmin(value_type& value, T upper) {
        if (value.maximum <= upper) return;
        assert(can_apply_chmin(value, upper));
        value.sum +=
            (upper - value.maximum) * T(value.maximum_count);
        if (value.minimum == value.maximum) {
            value.minimum = upper;
        } else if (value.second_minimum == value.maximum) {
            value.second_minimum = upper;
        }
        value.maximum = upper;
    }

    static constexpr bool can_apply_chmax(
        const value_type& value,
        T lower
    ) {
        return lower <= value.minimum ||
            value.minimum_count == value.length ||
            lower < value.second_minimum;
    }

    static constexpr void apply_chmax(value_type& value, T lower) {
        if (lower <= value.minimum) return;
        assert(can_apply_chmax(value, lower));
        value.sum +=
            (lower - value.minimum) * T(value.minimum_count);
        if (value.maximum == value.minimum) {
            value.maximum = lower;
        } else if (value.second_maximum == value.minimum) {
            value.second_maximum = lower;
        }
        value.minimum = lower;
    }

    static constexpr value_type constant_value(T value, int length) {
        return {
            value * T(length),
            value,
            negative_infinity,
            value,
            positive_infinity,
            length,
            length,
            length
        };
    }

   public:
    static constexpr value_type id() {
        return {
            T(0),
            negative_infinity,
            negative_infinity,
            positive_infinity,
            positive_infinity,
            0,
            0,
            0
        };
    }

    static constexpr value_type op(
        const value_type& left,
        const value_type& right
    ) {
        if (left.length == 0) return right;
        if (right.length == 0) return left;

        value_type result;
        result.sum = left.sum + right.sum;
        result.length = left.length + right.length;

        result.maximum = std::max(left.maximum, right.maximum);
        result.maximum_count = 0;
        result.second_maximum = negative_infinity;
        if (left.maximum == result.maximum) {
            result.maximum_count += left.maximum_count;
            result.second_maximum = std::max(
                result.second_maximum,
                left.second_maximum
            );
        } else {
            result.second_maximum = std::max(
                result.second_maximum,
                left.maximum
            );
        }
        if (right.maximum == result.maximum) {
            result.maximum_count += right.maximum_count;
            result.second_maximum = std::max(
                result.second_maximum,
                right.second_maximum
            );
        } else {
            result.second_maximum = std::max(
                result.second_maximum,
                right.maximum
            );
        }

        result.minimum = std::min(left.minimum, right.minimum);
        result.minimum_count = 0;
        result.second_minimum = positive_infinity;
        if (left.minimum == result.minimum) {
            result.minimum_count += left.minimum_count;
            result.second_minimum = std::min(
                result.second_minimum,
                left.second_minimum
            );
        } else {
            result.second_minimum = std::min(
                result.second_minimum,
                left.minimum
            );
        }
        if (right.minimum == result.minimum) {
            result.minimum_count += right.minimum_count;
            result.second_minimum = std::min(
                result.second_minimum,
                right.second_minimum
            );
        } else {
            result.second_minimum = std::min(
                result.second_minimum,
                right.minimum
            );
        }
        return result;
    }

    static constexpr operator_type op_id() {
        return {T(0), negative_infinity, positive_infinity};
    }

    // Returns f(g(x)).
    static constexpr operator_type op_comp(
        const operator_type& f,
        const operator_type& g
    ) {
        T lower = shift_lower_bound(g.lower, f.add);
        T upper = shift_upper_bound(g.upper, f.add);
        return {
            g.add + f.add,
            std::clamp(lower, f.lower, f.upper),
            std::clamp(upper, f.lower, f.upper)
        };
    }

    static constexpr bool can_apply(
        const operator_type& f,
        const value_type& value
    ) {
        if (value.length == 0 || f.lower == f.upper) return true;
        value_type mapped = value;
        apply_add(mapped, f.add);
        if (
            mapped.maximum <= f.lower ||
            f.upper <= mapped.minimum
        ) {
            return true;
        }
        if (!can_apply_chmax(mapped, f.lower)) return false;
        apply_chmax(mapped, f.lower);
        return can_apply_chmin(mapped, f.upper);
    }

    static constexpr value_type mapping(
        const operator_type& f,
        const value_type& value
    ) {
        assert(can_apply(f, value));
        if (value.length == 0) return value;
        if (f.lower == f.upper) {
            return constant_value(f.lower, value.length);
        }
        value_type result = value;
        apply_add(result, f.add);
        if (result.maximum <= f.lower) {
            return constant_value(f.lower, result.length);
        }
        if (f.upper <= result.minimum) {
            return constant_value(f.upper, result.length);
        }
        apply_chmax(result, f.lower);
        apply_chmin(result, f.upper);
        return result;
    }

    static constexpr value_type make(const T& value) {
        return constant_value(value, 1);
    }

    static constexpr operator_type make_chmin(const T& upper) {
        return {T(0), negative_infinity, upper};
    }

    static constexpr operator_type make_chmax(const T& lower) {
        return {T(0), lower, positive_infinity};
    }

    static constexpr operator_type make_add(const T& add) {
        return {add, negative_infinity, positive_infinity};
    }
};

}  // namespace beats_acted_monoid
}  // namespace m1une

m1une's library

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

Range Chmin/Chmax/Add Range Sum
(beats_acted_monoid/range_chmin_chmax_add_range_sum.hpp)

Overview

Template requirements

Interface and complexity

Example

Verified with

Code

Range Chmin/Chmax/Add Range Sum (beats_acted_monoid/range_chmin_chmax_add_range_sum.hpp)

Overview

Template requirements

Interface and complexity

Example

Verified with

Code

Range Chmin/Chmax/Add Range Sum
(beats_acted_monoid/range_chmin_chmax_add_range_sum.hpp)