algebra/monoid_s_f/monoid_sum_size_set.hpp

View this file on GitHub
Last update: 2024-03-24 17:17:53+09:00
Include: #include "algebra/monoid_s_f/monoid_sum_size_set.hpp"

Depends on

Verified with

verify/aoj_dsl/aoj_dsl_2_i_lazy_segment_tree.test.cpp

Code

#pragma once
#include "algebra/monoid_s/monoid_sum_size.hpp"
#include "algebra/monoid_f/monoid_set.hpp"
// MSF
template <class T> struct MonoidSumSizeSet {
    using MS = MonoidSumSize<T>;
    using MF = MonoidSet<T>;
    using S = typename MS::S;
    using F = typename MF::F;
    static constexpr S mapping(F f, S x) { return (f == MF::id() ? x : std::make_pair(f * x.second, x.second)); }
};

#line 2 "algebra/monoid_s/monoid_sum_size.hpp"
// MS
template <class T> struct MonoidSumSize {
    using S = std::pair<T, int>;
    static constexpr S op(S a, S b) { return {a.first + b.first, a.second + b.second}; }
    static constexpr S e() { return {T(0), 0}; }
};
#line 2 "algebra/monoid_f/monoid_set.hpp"
// MF
template <class T> struct MonoidSet {
    using F = T;
    static constexpr F composition(F f, F g) { return f == id() ? g : f; }
    static constexpr F id() { return std::numeric_limits<F>::max(); }
};
#line 4 "algebra/monoid_s_f/monoid_sum_size_set.hpp"
// MSF
template <class T> struct MonoidSumSizeSet {
    using MS = MonoidSumSize<T>;
    using MF = MonoidSet<T>;
    using S = typename MS::S;
    using F = typename MF::F;
    static constexpr S mapping(F f, S x) { return (f == MF::id() ? x : std::make_pair(f * x.second, x.second)); }
};