Monoid: Argmin
(algebra/monoid_argmin.hpp)

• View this file on GitHub
• Last update: 2026-10-23 22:06:19+09:00
• Include: #include "algebra/monoid_argmin.hpp"

Required by

• Plus Minus One RMQ (datastructure/plus_minus_one_rmq.hpp)
• 最小共通祖先(LCA) (graph/lowest_common_ancestor.hpp)
• Manhattan MST (graph/manhattan_mst.hpp)

Verified with

• test/library-checker/lca.test.cpp
• test/library-checker/manhattanmst.test.cpp
• test/unit/monoid.test.cpp
• test/unit/sparse_table.test.cpp

Code

#pragma once
#include <limits>
template <class T>
struct monoid_argmin {
    struct S {
        T val;
        int id;
    };
    static S op(S a, S b) {
        if (a.val != b.val) return a.val < b.val ? a : b;
        return a.id < b.id ? a : b;
    }
    static S e() {
        return {std::numeric_limits<T>::max(), -1};
    }
};

#line 2 "algebra/monoid_argmin.hpp"
#include <limits>
template <class T>
struct monoid_argmin {
    struct S {
        T val;
        int id;
    };
    static S op(S a, S b) {
        if (a.val != b.val) return a.val < b.val ? a : b;
        return a.id < b.id ? a : b;
    }
    static S e() {
        return {std::numeric_limits<T>::max(), -1};
    }
};

Back to top page