algebra/monoid_s_f/monoid_sum_size_affine.hpp

View this file on GitHub
Last update: 2024-03-24 17:04:51+09:00
Include: #include "algebra/monoid_s_f/monoid_sum_size_affine.hpp"
Link: https://atcoder.jp/contests/practice2/tasks/practice2_k

Depends on

Verified with

verify/lc_data_structure/lc_range_affine_range_sum.test.cpp

Code

#pragma once
#include "algebra/monoid_s/monoid_sum_size.hpp"
#include "algebra/monoid_f/monoid_affine.hpp"
// https://atcoder.jp/contests/practice2/tasks/practice2_k
// MSF
template <class T> struct MonoidSumSizeAffine {
    using MS = MonoidSumSize<T>;
    using MF = MonoidAffine<T>;
    using S = typename MS::S;
    using F = typename MF::F;
    static constexpr S mapping(F f, S x) { return {f.first * x.first + f.second * 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_affine.hpp"
// MF
template <class T> struct MonoidAffine {
    using F = std::pair<T, T>;  // a * x + b -> {a, b}
    // f(x) = f.first * x + f.second, g(x) = g.first * x + g.second
    // f(g(x)) = f.first * (g.first * x + g.second) + f.second
    //         = f.first * g.first * x + f.first * g.second + f.second
    static constexpr F composition(F f, F g) { return {f.first * g.first, f.first * g.second + f.second}; }
    static constexpr F id() { return {T(1), T(0)}; }
};
#line 4 "algebra/monoid_s_f/monoid_sum_size_affine.hpp"
// https://atcoder.jp/contests/practice2/tasks/practice2_k
// MSF
template <class T> struct MonoidSumSizeAffine {
    using MS = MonoidSumSize<T>;
    using MF = MonoidAffine<T>;
    using S = typename MS::S;
    using F = typename MF::F;
    static constexpr S mapping(F f, S x) { return {f.first * x.first + f.second * x.second, x.second}; }
};