Acted Monoid Wrapper
(acted_monoid/wrapper.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "acted_monoid/wrapper.hpp"

Overview

Wrapper provides a convenient way to define an Acted Monoid inline without writing a separate struct. This is particularly useful during contests when you need to combine custom mapping logic quickly.

It uses C++20 non-type template parameters (NTTPs), allowing functions, structural function objects, and captureless lambda values to be passed as template arguments. The template arguments must be valid constant template arguments, but IsActedMonoid does not require the operations themselves to be callable in a constant expression.

Template Parameters

• typename T: The type of the value element (value_type).
• typename E: The type of the operator element (operator_type).
• auto Op: A function or lambda for the value monoid operation (T op(T, T)).
• auto Id: A function or lambda returning the value identity (T id()).
• auto OpComp: A function or lambda for operator composition (E op_comp(E, E)).
• auto OpId: A function or lambda returning the operator identity (E op_id()).
• auto Mapping: A function or lambda for mapping the operator onto the value (T mapping(E, T)).
• bool Commutative: Whether the value operation Op is commutative. Defaults to false.
• bool OperatorCommutative: Whether the operator operation OpComp is commutative. Defaults to false.

Example

#include "acted_monoid/wrapper.hpp"

// Definition of Range Add Range Min using Wrapper
constexpr long long INF = std::numeric_limits<long long>::max();
using RangeAddRangeMin = m1une::acted_monoid::Wrapper<
    long long,
    long long,
    [](long long a, long long b) { return std::min(a, b); },
    []() { return INF; },
    [](long long f, long long g) { return f + g; },
    []() { return 0LL; },
    [](long long f, long long x) { return x == INF ? INF : x + f; },
    true,
    true
>;

Interface and Complexity

Wrapper exposes value_type, operator_type, commutative, operator_commutative, id(), op(a, b), op_id(), op_comp(f, g), and mapping(f, x) for lazy data structures.

Each static operation forwards to the function or lambda supplied as the corresponding template parameter, so its complexity is the cost of that callable.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_WRAPPER_HPP
#define M1UNE_ACTED_MONOID_WRAPPER_HPP 1

namespace m1une {
namespace acted_monoid {

// Wrapper struct to generate an Acted Monoid using Non-Type Template Parameters (NTTP).
// Useful for quickly defining acted monoids using callables supplied as NTTPs during contests.
template <typename T, typename E, auto Op, auto Id, auto OpComp, auto OpId, auto Mapping,
          bool Commutative = false, bool OperatorCommutative = false>
struct Wrapper {
    using value_type = T;
    using operator_type = E;
    static constexpr bool commutative = Commutative;
    static constexpr bool operator_commutative = OperatorCommutative;

    // Returns the identity element of the value monoid.
    static constexpr T id() {
        return Id();
    }

    // Returns the result of the value monoid binary operation.
    static constexpr T op(const T& a, const T& b) {
        return Op(a, b);
    }

    // Returns the identity element of the operator monoid.
    static constexpr E op_id() {
        return OpId();
    }

    // Composes two operations f and g (corresponds to f(g(x))).
    static constexpr E op_comp(const E& f, const E& g) {
        return OpComp(f, g);
    }

    // Applies the operator f onto the value x.
    static constexpr T mapping(const E& f, const T& x) {
        return Mapping(f, x);
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_WRAPPER_HPP

#line 1 "acted_monoid/wrapper.hpp"



namespace m1une {
namespace acted_monoid {

// Wrapper struct to generate an Acted Monoid using Non-Type Template Parameters (NTTP).
// Useful for quickly defining acted monoids using callables supplied as NTTPs during contests.
template <typename T, typename E, auto Op, auto Id, auto OpComp, auto OpId, auto Mapping,
          bool Commutative = false, bool OperatorCommutative = false>
struct Wrapper {
    using value_type = T;
    using operator_type = E;
    static constexpr bool commutative = Commutative;
    static constexpr bool operator_commutative = OperatorCommutative;

    // Returns the identity element of the value monoid.
    static constexpr T id() {
        return Id();
    }

    // Returns the result of the value monoid binary operation.
    static constexpr T op(const T& a, const T& b) {
        return Op(a, b);
    }

    // Returns the identity element of the operator monoid.
    static constexpr E op_id() {
        return OpId();
    }

    // Composes two operations f and g (corresponds to f(g(x))).
    static constexpr E op_comp(const E& f, const E& g) {
        return OpComp(f, g);
    }

    // Applies the operator f onto the value x.
    static constexpr T mapping(const E& f, const T& x) {
        return Mapping(f, x);
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page