monoid/monoid_addsz.hpp

• View this file on GitHub
• Last update: 2025-10-01 15:41:05+09:00
• Include: #include "monoid/monoid_addsz.hpp"
• Link: View error logs on GitHub Actions

Depends on

• Monoid (monoid/monoid.hpp)

Required by

• monoid/acted_monoids/range_add_range_sum.hpp
• monoid/acted_monoids/range_affine_range_sum.hpp
• monoid/acted_monoids/range_update_range_sum.hpp
• monoid/prim_acted_monoids.hpp

Verified with

• verify/unit_test/lazy_segtree.test.cpp

Code

#ifndef M1UNE_MONOID_ADDSZ_HPP
#define M1UNE_MONOID_ADDSZ_HPP 1

#include <concepts>

#include "monoid.hpp"

namespace m1une {

template <typename T>
struct value_and_size {
    T value;
    int size;
};

template <Monoid M>
using monoid_addsz = monoid<value_and_size<typename M::value_type>,
                            [](value_and_size<typename M::value_type> a, value_and_size<typename M::value_type> b) {
                                return value_and_size<typename M::value_type>{M::op(a.value, b.value), a.size + b.size};
                            },
                            []() { return value_and_size<typename M::value_type>{M::id(), 0}; }, M::is_commutative>;

}  // namespace m1une

#endif  // M1UNE_MONOID_ADDSZ_HPP

#line 1 "monoid/monoid_addsz.hpp"



#include <concepts>

#line 1 "monoid/monoid.hpp"



#line 5 "monoid/monoid.hpp"
#include <functional>
#include <type_traits>

namespace m1une {

template <typename T, auto operation, auto identity, bool commutative>
struct monoid {
    static_assert(std::is_invocable_r_v<T, decltype(operation), T, T>, "operation must work as T(T, T)");
    static_assert(std::is_invocable_r_v<T, decltype(identity)>, "identity must work as T()");

    using value_type = T;
    static constexpr auto op = operation;
    static constexpr auto id = identity;
    static constexpr bool is_commutative = commutative;
};

template <typename T>
concept Monoid = requires(typename T::value_type v) {
    typename T::value_type;
    { T::op(v, v) } -> std::same_as<typename T::value_type>;
    { T::id() } -> std::same_as<typename T::value_type>;
    { T::is_commutative } -> std::convertible_to<bool>;
};

}  // namespace m1une


#line 7 "monoid/monoid_addsz.hpp"

namespace m1une {

template <typename T>
struct value_and_size {
    T value;
    int size;
};

template <Monoid M>
using monoid_addsz = monoid<value_and_size<typename M::value_type>,
                            [](value_and_size<typename M::value_type> a, value_and_size<typename M::value_type> b) {
                                return value_and_size<typename M::value_type>{M::op(a.value, b.value), a.size + b.size};
                            },
                            []() { return value_and_size<typename M::value_type>{M::id(), 0}; }, M::is_commutative>;

}  // namespace m1une

Back to top page