Src/Algebra/Monoid/ChminMonoid.hpp

• View this file on GitHub
• Last update: 2024-02-10 00:53:33+09:00
• Include: #include "Src/Algebra/Monoid/ChminMonoid.hpp"

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

• Auxiliary Tree (指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木) (Src/Graph/Tree/AuxiliaryTree.hpp)
• Lowest Common Ancestor (Src/Graph/Tree/LowestCommonAncestor.hpp)

Verified with

• Test/AtCoder/abc340_g.test.cpp
• ABC359-G Sum of Tree Distance (Test/AtCoder/abc359_g.test.cpp)
• Test/CF/CF923-D.test.cpp
• Test/LC/lca/LowestCommonAncestor.test.cpp
• Test/Manual/typical90_ai.test.cpp
• Test/My/Graph/Tree/LowestCommonAncestor.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"

#include <algorithm>
#include <optional>

namespace zawa {

template <class T, class U>
class ChminMonoidData {
private:
    std::optional<T> priority_{};
    U value_{};
public:
    ChminMonoidData() = default;
    ChminMonoidData(const U& value)
        : priority_{std::nullopt}, value_{value} {}
    ChminMonoidData(const T& priority, const U& value)
        : priority_{priority}, value_{value} {}

    constexpr bool infty() const noexcept {
        return !priority_.has_value();
    }
    constexpr const T& priority() const noexcept {
        return priority_.value();
    }
    constexpr const U& value() const noexcept {
        return value_;
    }
    friend constexpr bool operator<(const ChminMonoidData& l, const ChminMonoidData& r) {
        if (l.infty()) return false;
        else if (r.infty()) return true;
        else return l.priority() < r.priority();
    }
};

template <class T, class U>
struct ChminMonoid {
    using Element = ChminMonoidData<T, U>;
    static Element identity() noexcept {
        return Element{};
    }
    // タイブレークはl側を優先するようになっている。
    static Element operation(const Element& l, const Element& r) noexcept {
        return (r < l ? r : l);
    }
};

} // namespace zawa

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

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Algebra/Monoid/ChminMonoid.hpp"

#include <algorithm>
#include <optional>

namespace zawa {

template <class T, class U>
class ChminMonoidData {
private:
    std::optional<T> priority_{};
    U value_{};
public:
    ChminMonoidData() = default;
    ChminMonoidData(const U& value)
        : priority_{std::nullopt}, value_{value} {}
    ChminMonoidData(const T& priority, const U& value)
        : priority_{priority}, value_{value} {}

    constexpr bool infty() const noexcept {
        return !priority_.has_value();
    }
    constexpr const T& priority() const noexcept {
        return priority_.value();
    }
    constexpr const U& value() const noexcept {
        return value_;
    }
    friend constexpr bool operator<(const ChminMonoidData& l, const ChminMonoidData& r) {
        if (l.infty()) return false;
        else if (r.infty()) return true;
        else return l.priority() < r.priority();
    }
};

template <class T, class U>
struct ChminMonoid {
    using Element = ChminMonoidData<T, U>;
    static Element identity() noexcept {
        return Element{};
    }
    // タイブレークはl側を優先するようになっている。
    static Element operation(const Element& l, const Element& r) noexcept {
        return (r < l ? r : l);
    }
};

} // namespace zawa

Back to top page