monoid/prim_acted_monoids.hpp

View this file on GitHub
Last update: 2025-10-01 15:41:05+09:00
Include: #include "monoid/prim_acted_monoids.hpp"

Depends on

Code

#ifndef M1UNE_PRIM_ACTED_MONOIDS_HPP
#define M1UNE_PRIM_ACTED_MONOIDS_HPP 1

#include "acted_monoid.hpp"
#include "acted_monoids/range_add_range_min.hpp"
#include "acted_monoids/range_add_range_max.hpp"
#include "acted_monoids/range_add_range_sum.hpp"
#include "acted_monoids/range_update_range_min.hpp"
#include "acted_monoids/range_update_range_max.hpp"
#include "acted_monoids/range_update_range_sum.hpp"
#include "acted_monoids/range_affine_range_minmax.hpp"
#include "acted_monoids/range_affine_range_sum.hpp"

#endif  // M1UNE_PRIM_ACTED_MONOIDS_HPP

#line 1 "monoid/prim_acted_monoids.hpp"



#line 1 "monoid/acted_monoid.hpp"



#include <concepts>
#include <functional>
#include <type_traits>

#line 1 "monoid/monoid.hpp"



#line 7 "monoid/monoid.hpp"

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 9 "monoid/acted_monoid.hpp"

namespace m1une {

template <Monoid Data, Monoid Act, auto mapping>
struct acted_monoid {
    using data_monoid = Data;
    using act_monoid = Act;

    using data_type = typename Data::value_type;
    using act_type = typename Act::value_type;

    static_assert(std::is_invocable_r_v<data_type, decltype(mapping), act_type, data_type>,
                  "mapping must work as data_type(act_type, data_type)");

    static constexpr auto data_op = Data::op;
    static constexpr auto data_id = Data::id;
    static constexpr bool data_is_commutative = Data::is_commutative;
    static constexpr auto act_op = Act::op;
    static constexpr auto act_id = Act::id;
    static constexpr bool act_is_commutative = Act::is_commutative;
    static constexpr auto apply = mapping;
};

template <typename T>
concept ActedMonoid = requires(typename T::data_type d, typename T::act_type a) {
    typename T::data_monoid;
    typename T::act_monoid;
    typename T::data_type;
    typename T::act_type;
    requires Monoid<typename T::data_monoid>;
    requires Monoid<typename T::act_monoid>;
    { T::apply(a, d) } -> std::same_as<typename T::data_type>;
};

}  // namespace m1une


#line 1 "monoid/acted_monoids/range_add_range_min.hpp"



#line 1 "monoid/monoids/add_monoid.hpp"



#line 5 "monoid/monoids/add_monoid.hpp"

namespace m1une {

template <typename T>
using add_monoid = monoid<T, [](T a, T b) { return a + b; }, []() { return T(0); }, true>;

}  // namespace m1une


#line 1 "monoid/monoids/min_monoid.hpp"



#include <algorithm>
#include <limits>

#line 8 "monoid/monoids/min_monoid.hpp"

namespace m1une {

template <typename T>
using min_monoid =
    monoid<T, [](T a, T b) { return std::min(a, b); }, []() { return std::numeric_limits<T>::max(); }, true>;

}  // namespace m1une


#line 7 "monoid/acted_monoids/range_add_range_min.hpp"

namespace m1une {

template <typename T>
using range_add_range_min_monoid = acted_monoid<min_monoid<T>, add_monoid<T>, [](T a, T x) { return a + x; }>;

}  // namespace m1une


#line 1 "monoid/acted_monoids/range_add_range_max.hpp"



#line 1 "monoid/monoids/max_monoid.hpp"



#line 6 "monoid/monoids/max_monoid.hpp"

#line 8 "monoid/monoids/max_monoid.hpp"

namespace m1une {

template <typename T>
using max_monoid =
    monoid<T, [](T a, T b) { return std::max(a, b); }, []() { return std::numeric_limits<T>::min(); }, true>;

}  // namespace m1une


#line 7 "monoid/acted_monoids/range_add_range_max.hpp"

namespace m1une {

template <typename T>
using range_add_range_max_monoid = acted_monoid<max_monoid<T>, add_monoid<T>, [](T a, T x) { return a + x; }>;

}  // namespace m1une


#line 1 "monoid/acted_monoids/range_add_range_sum.hpp"



#line 1 "monoid/monoid_addsz.hpp"



#line 5 "monoid/monoid_addsz.hpp"

#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


#line 7 "monoid/acted_monoids/range_add_range_sum.hpp"

namespace m1une {

template <typename T>
using range_add_range_sum_monoid =
    acted_monoid<monoid_addsz<add_monoid<T>>, add_monoid<T>,
                 [](T a, typename monoid_addsz<add_monoid<T>>::data_type x) {
                     return typename monoid_addsz<add_monoid<T>>::data_type{x.value + a * x.size, x.size};
                 }>;

}  // namespace m1une


#line 1 "monoid/acted_monoids/range_update_range_min.hpp"



#line 1 "monoid/monoids/update_monoid.hpp"



#line 5 "monoid/monoids/update_monoid.hpp"

namespace m1une {

template <typename T, T identity>
using update_monoid = monoid<T,
                             [](T a, T b) {
                                 if (b == identity) return a;
                                 return b;
                             },
                             []() { return identity; }, false>;

}  // namespace m1une


#line 7 "monoid/acted_monoids/range_update_range_min.hpp"

namespace m1une {

template <typename T, T identity>
using range_update_range_max = acted_monoid<min_monoid<T>, update_monoid<T, identity>, [](T x, T a) {
    if (a == identity) return x;
    return a;
}>;

}  // namespace m1une


#line 1 "monoid/acted_monoids/range_update_range_max.hpp"



#line 7 "monoid/acted_monoids/range_update_range_max.hpp"

namespace m1une {

template <typename T, T identity>
using range_update_range_max = acted_monoid<max_monoid<T>, update_monoid<T, identity>, [](T x, T a) {
    if (a == identity) return x;
    return a;
}>;

}  // namespace m1une


#line 1 "monoid/acted_monoids/range_update_range_sum.hpp"



#line 8 "monoid/acted_monoids/range_update_range_sum.hpp"

namespace m1une {

template <typename T, T identity>
using range_update_range_sum_monoid =
    acted_monoid<monoid_addsz<add_monoid<T>>, update_monoid<T, identity>,
                 [](T a, typename monoid_addsz<add_monoid<T>>::data_type x) {
                     if (a == identity) return x;
                     return typename monoid_addsz<add_monoid<T>>::data_type{a * x.size, x.size};
                 }>;

}  // namespace m1une


#line 1 "monoid/acted_monoids/range_affine_range_minmax.hpp"



#line 1 "monoid/monoids/affine_monoid.hpp"



#include <utility>

#line 7 "monoid/monoids/affine_monoid.hpp"

namespace m1une {

// Affine transformation f(x) = ax + b is represented as (a, b)
// perform f first, then g
// op(f, g)(x) = g(f(x))
template <typename T>
using affine_monoid = monoid<std::pair<T, T>,
                             [](std::pair<T, T> f, std::pair<T, T> g) {
                                 return std::pair<T, T>(f.first * g.first, f.second * g.first + g.second);
                             },
                             []() { return std::pair<T, T>(1, 0); }, false>;

}  // namespace m1une


#line 1 "monoid/monoids/minmax_monoid.hpp"



#line 7 "monoid/monoids/minmax_monoid.hpp"

#line 9 "monoid/monoids/minmax_monoid.hpp"

namespace m1une {

// Monoid for storing both a minimum and maximum value.
// The operation combines two pairs by taking the component-wise min and max.
template <typename T>
using minmax_monoid =
    monoid<std::pair<T, T>,
           [](std::pair<T, T> a, std::pair<T, T> b) {
               return std::pair<T, T>(std::min(a.first, b.first), std::max(a.second, b.second));
           },
           []() { return std::pair<T, T>(std::numeric_limits<T>::max(), std::numeric_limits<T>::lowest()); }, true>;

}  // namespace m1une


#line 7 "monoid/acted_monoids/range_affine_range_minmax.hpp"

namespace m1une {

// Acted monoid for range affine transformations and range min/max queries.
template <typename T>
using range_affine_range_minmax_monoid =
    acted_monoid<minmax_monoid<T>, affine_monoid<T>,
                 [](typename affine_monoid<T>::value_type f, typename minmax_monoid<T>::value_type x) {
                     auto v1 = f.first * x.first + f.second;
                     auto v2 = f.first * x.second + f.second;
                     return std::pair<T, T>(std::min(v1, v2), std::max(v1, v2));
                 }>;

}  // namespace m1une


#line 1 "monoid/acted_monoids/range_affine_range_sum.hpp"



#line 8 "monoid/acted_monoids/range_affine_range_sum.hpp"

namespace m1une {

template <typename T>
using range_affine_range_sum_monoid =
    acted_monoid<monoid_addsz<add_monoid<T>>, affine_monoid<T>,
                 [](typename affine_monoid<T>::value_type f, typename monoid_addsz<add_monoid<T>>::value_type x) {
                     // f = (a, b) is the affine transformation
                     // x = {value, size} is the data (sum and size of the range)
                     // Applying f to each element xi and summing up:
                     // sum(a*xi + b) = a * sum(xi) + b * size
                     return typename monoid_addsz<add_monoid<T>>::value_type{f.first * x.value + f.second * x.size,
                                                                             x.size};
                 }>;

}  // namespace m1une


#line 13 "monoid/prim_acted_monoids.hpp"

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

monoid/prim_acted_monoids.hpp

Depends on

Code