monoids/plus_min_action.hpp

• View this file on GitHub
• Last update: 2021-08-30 04:35:37+09:00
• Include: #include "monoids/plus_min_action.hpp"

Depends on

• monoids/min.hpp
• monoids/plus.hpp

Verified with

• data_structure/lazy_propagation_segment_tree.range_min_range_add.test.cpp
• utils/mo_algorithm.yuki1270.test.cpp

Code

#pragma once
#include "../monoids/plus.hpp"
#include "../monoids/min.hpp"

template <class T>
struct plus_min_action {
    typename min_monoid<T>::value_type operator () (typename plus_monoid<T>::value_type f, typename min_monoid<T>::value_type x) const {
        return (x == min_monoid<T>().unit() ? x : f + x);
    }
};

#line 2 "monoids/plus.hpp"

template <class T>
struct plus_monoid {
    typedef T value_type;
    value_type unit() const { return value_type(); }
    value_type mult(value_type a, value_type b) const { return 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); }
};
#line 4 "monoids/plus_min_action.hpp"

template <class T>
struct plus_min_action {
    typename min_monoid<T>::value_type operator () (typename plus_monoid<T>::value_type f, typename min_monoid<T>::value_type x) const {
        return (x == min_monoid<T>().unit() ? x : f + x);
    }
};

Back to top page