Src/Algebra/Monoid/MinCountMonoid.hpp

• View this file on GitHub
• Last update: 2024-11-05 03:06:10+09:00
• Include: #include "Src/Algebra/Monoid/MinCountMonoid.hpp"

Required by

• Src/Utility/AreaOfUnionOfRectangles.hpp

Verified with

• Test/AtCoder/abc346_g.test.cpp
• Test/LC/area_of_union_of_rectangles.test.cpp

Code

#pragma once

#include <limits>
#include <utility>

namespace zawa {

template <class T, class U>
struct MinCountMonoid {
    // min, countの順
    using Element = std::pair<T, U>;

    static Element identity() noexcept {
        return { std::numeric_limits<T>::max(), U{} };
    }

    static Element operation(const Element& L, const Element& R) {
        if (L.first < R.first) return L;
        else if (L.first > R.first) return R;
        else return Element{ L.first, L.second + R.second };
    }

};

} // namespace 

#line 2 "Src/Algebra/Monoid/MinCountMonoid.hpp"

#include <limits>
#include <utility>

namespace zawa {

template <class T, class U>
struct MinCountMonoid {
    // min, countの順
    using Element = std::pair<T, U>;

    static Element identity() noexcept {
        return { std::numeric_limits<T>::max(), U{} };
    }

    static Element operation(const Element& L, const Element& R) {
        if (L.first < R.first) return L;
        else if (L.first > R.first) return R;
        else return Element{ L.first, L.second + R.second };
    }

};

} // namespace 

Back to top page