algebra/acted_monoid/acted_monoid_max_index_plus.hpp

View this file on GitHub
Last update: 2026-04-11 00:41:57+09:00
Include: #include "algebra/acted_monoid/acted_monoid_max_index_plus.hpp"

Depends on

Verified with

segment_tree/test/lazy_segment_tree_min_index_plus.test.cpp

Code

#pragma once

#include "../monoid/monoid_max_index.hpp"
#include "../monoid/monoid_plus.hpp"

template <class T, T inf, bool smaller_index> struct ActedMonoidMaxIndexPlus {
    using MS = MonoidMaxIndex<T, inf, smaller_index>;
    using MF = MonoidPlus<T>;
    using S = typename MS::value_type;
    using F = typename MF::value_type;
    static constexpr S mapping(const F f, const S x, const int size) {
        if (f == MF::identity()) {
            return {x.v, x.i};
        }
        return {x.v + f, x.i};
    }
};

#line 2 "algebra/acted_monoid/acted_monoid_max_index_plus.hpp"

#line 2 "algebra/monoid/monoid_max_index.hpp"

#line 2 "algebra/value_index.hpp"

template <class T> struct ValueIndex {
    T v;
    int i;
    friend std::ostream& operator<<(std::ostream& os, const ValueIndex& x) {
        return os << x.v;
    }
};
#line 4 "algebra/monoid/monoid_max_index.hpp"

template <class T, T inf, bool smaller_index> struct MonoidMaxIndex {
    using value_type = ValueIndex<T>;
    static constexpr value_type operation(const value_type& a,
                                          const value_type& b) {
        if (a.v > b.v) return a;
        if (a.v < b.v) return b;
        bool is_small = smaller_index ? (a.i < b.i) : (a.i >= b.i);
        return is_small ? a : b;
    }
    static constexpr value_type identity() noexcept { return {-inf, -1}; }
    static constexpr bool commutative = true;
};
#line 2 "algebra/monoid/monoid_plus.hpp"

template <class T> struct MonoidPlus {
    using value_type = T;
    static constexpr T operation(const T& a, const T& b) noexcept {
        return a + b;
    }
    static constexpr T identity() noexcept { return T(0); }
    static constexpr T inverse(const T& a) noexcept { return -a; }
    static constexpr bool commutative = true;
};
#line 5 "algebra/acted_monoid/acted_monoid_max_index_plus.hpp"

template <class T, T inf, bool smaller_index> struct ActedMonoidMaxIndexPlus {
    using MS = MonoidMaxIndex<T, inf, smaller_index>;
    using MF = MonoidPlus<T>;
    using S = typename MS::value_type;
    using F = typename MF::value_type;
    static constexpr S mapping(const F f, const S x, const int size) {
        if (f == MF::identity()) {
            return {x.v, x.i};
        }
        return {x.v + f, x.i};
    }
};