misc/monoids.hpp

• View this file on GitHub
• Last update: 2025-02-22 20:23:26+09:00
• Include: #include "misc/monoids.hpp"

Required by

• data_structure/offline_rectangle_sum.hpp

Verified with

• test/data_structure/Point_Add_Rectangle_Sum.test.cpp
• test/data_structure/Rectangle_Sum.test.cpp
• test/data_structure/Static_Range_Inversions_Query.test.cpp
• test/data_structure/aoj_dsl_1_b.test.cpp

Code

#pragma once

#include<limits>

namespace noya2{

template<typename T>
struct max_monoid {
    using value_type = T;
    static constexpr T op(const T &a, const T &b){ return max(a,b); }
    static constexpr T e(){ return std::numeric_limits<T>::min(); }
    static constexpr T inv(const T &a){ return e(); }
};
template<typename T>
struct min_monoid {
    using value_type = T;
    static constexpr T op(const T &a, const T &b){ return min(a,b); }
    static constexpr T e(){ return std::numeric_limits<T>::max(); }
    static constexpr T inv(const T &a){ return e(); }
};
template<typename T>
struct plus_group {
    using value_type = T;
    static constexpr T op(const T &a, const T &b){ return a + b; }
    static constexpr T e(){ return T(0); }
    static constexpr T inv(const T &a){ return -a; }
};
template<typename T>
struct xor_group {
    using value_type = T;
    static constexpr T op(const T &a, const T &b){ return a ^ b; }
    static constexpr T e(){ return T(0); }
    static constexpr T inv(const T &a){ return a; }
};

template<class S, auto _op, auto _e>
struct monoid {
    using value_type = S;
    static constexpr value_type op(value_type a, value_type b){
        return _op(a, b);
    }
    static constexpr value_type e(){
        return _e();
    }
};
  
} // namespace noya2

#line 2 "misc/monoids.hpp"

#include<limits>

namespace noya2{

template<typename T>
struct max_monoid {
    using value_type = T;
    static constexpr T op(const T &a, const T &b){ return max(a,b); }
    static constexpr T e(){ return std::numeric_limits<T>::min(); }
    static constexpr T inv(const T &a){ return e(); }
};
template<typename T>
struct min_monoid {
    using value_type = T;
    static constexpr T op(const T &a, const T &b){ return min(a,b); }
    static constexpr T e(){ return std::numeric_limits<T>::max(); }
    static constexpr T inv(const T &a){ return e(); }
};
template<typename T>
struct plus_group {
    using value_type = T;
    static constexpr T op(const T &a, const T &b){ return a + b; }
    static constexpr T e(){ return T(0); }
    static constexpr T inv(const T &a){ return -a; }
};
template<typename T>
struct xor_group {
    using value_type = T;
    static constexpr T op(const T &a, const T &b){ return a ^ b; }
    static constexpr T e(){ return T(0); }
    static constexpr T inv(const T &a){ return a; }
};

template<class S, auto _op, auto _e>
struct monoid {
    using value_type = S;
    static constexpr value_type op(value_type a, value_type b){
        return _op(a, b);
    }
    static constexpr value_type e(){
        return _e();
    }
};
  
} // namespace noya2

Back to top page