Range Add Range ArgMax
(acted_monoid/range_add_range_arg_max.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "acted_monoid/range_add_range_arg_max.hpp"

Overview

An acted monoid for range addition and range maximum queries with the position of the selected maximum.

Tie-breaking

If there are multiple maximum values in the queried range, the op function returns the earliest order.

Example

using AM = m1une::acted_monoid::RangeAddRangeArgMax<long long>;
m1une::ds::LazySegtree<AM> seg(A);
auto q = seg.prod(0, A.size());
std::cout << q.max_val << " " << q.ord << "\n";

Interface and Complexity

This is a stateless acted-monoid tag. Lazy data structures use its public value_type, operator_type, id(), op(a, b), op_id(), op_comp(f, g), and mapping(f, x) members. Helpers such as make(...), shifted mappings, or reversal-aware mappings are described above when the header provides them.

The static operations are $O(1)$ for the scalar metadata stored by these range acted monoids, aside from the cost of the underlying arithmetic type.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_ARG_MAX_HPP
#define M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_ARG_MAX_HPP 1

#include <limits>

namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeAddRangeArgMaxNode {
    T max_val;
    long long size;
    long long ord;
};

// Acted Monoid for Range Addition and Range Maximum Value & Index queries.
template <typename T>
struct RangeAddRangeArgMax {
    using value_type = RangeAddRangeArgMaxNode<T>;
    using operator_type = T;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = true;

    static constexpr value_type id() {
        return {std::numeric_limits<T>::lowest(), 0, -1};
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        if (a.size == 0) return b;
        if (b.size == 0) return a;
        long long size = a.size + b.size;
        if (a.max_val >= b.max_val) return {a.max_val, size, a.ord};
        return {b.max_val, size, b.ord + a.size};
    }

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

    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f + g;
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x.size == 0) return x;
        return {x.max_val + f, x.size, x.ord};
    }

    static constexpr value_type make(const T& val) {
        return {val, 1, 0};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_ADD_RANGE_ARG_MAX_HPP

#line 1 "acted_monoid/range_add_range_arg_max.hpp"



#include <limits>

namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeAddRangeArgMaxNode {
    T max_val;
    long long size;
    long long ord;
};

// Acted Monoid for Range Addition and Range Maximum Value & Index queries.
template <typename T>
struct RangeAddRangeArgMax {
    using value_type = RangeAddRangeArgMaxNode<T>;
    using operator_type = T;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = true;

    static constexpr value_type id() {
        return {std::numeric_limits<T>::lowest(), 0, -1};
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        if (a.size == 0) return b;
        if (b.size == 0) return a;
        long long size = a.size + b.size;
        if (a.max_val >= b.max_val) return {a.max_val, size, a.ord};
        return {b.max_val, size, b.ord + a.size};
    }

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

    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f + g;
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x.size == 0) return x;
        return {x.max_val + f, x.size, x.ord};
    }

    static constexpr value_type make(const T& val) {
        return {val, 1, 0};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page