algebra/monoid/monoid_min_index.hpp

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

Depends on

• algebra/value_index.hpp

Required by

• algebra/acted_monoid/acted_monoid_min_index_plus.hpp

Verified with

• segment_tree/test/lazy_segment_tree_min_index_plus.test.cpp

Code

#pragma once

#include "../../algebra/value_index.hpp"

template <class T, T inf, bool smaller_index> struct MonoidMinIndex {
    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_min_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_min_index.hpp"

template <class T, T inf, bool smaller_index> struct MonoidMinIndex {
    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;
};

Back to top page