monoids/min.hpp

• View this file on GitHub
• Last update: 2019-12-27 19:16:13+09:00
• Include: #include "monoids/min.hpp"

Required by

• monoids/plus_min_action.hpp
• Longest Common Prefix / 最長共通接頭辞 (接尾辞配列, 前処理 $O(N (\log N)^2)$ + $O(1)$) (string/longest_common_prefix.hpp)
• Length of Left-to-right Maxima (前処理 $O(n \log n)$ + $O(1)$) (utils/left_to_right_maxima.hpp)

Verified with

• data_structure/lazy_propagation_segment_tree.range_min_range_add.test.cpp
• data_structure/sparse_table.yosupo.test.cpp
• graph/cartesian_tree.yukicoder-1031.test.cpp
• string/longest_common_prefix.yosupo.test.cpp

Code

#pragma once
#include <algorithm>
#include <limits>

template <class T>
struct min_monoid {
    typedef T value_type;
    value_type unit() const { return std::numeric_limits<T>::max(); }
    value_type mult(value_type a, value_type b) const { return std::min(a, b); }
};

#line 2 "monoids/min.hpp"
#include <algorithm>
#include <limits>

template <class T>
struct min_monoid {
    typedef T value_type;
    value_type unit() const { return std::numeric_limits<T>::max(); }
    value_type mult(value_type a, value_type b) const { return std::min(a, b); }
};

Back to top page