This documentation is automatically generated by online-judge-tools/verification-helper
#include "alg/acted_monoid/cntsum_affine.hpp"
#include "alg/monoid/add_pair.hpp"
#include "alg/monoid/affine.hpp"
template <typename E>
struct ActedMonoid_CntSum_Affine {
using Monoid_X = Monoid_Add_Pair<E>;
using Monoid_A = Monoid_Affine<E>;
using X = typename Monoid_X::value_type;
using A = typename Monoid_A::value_type;
static constexpr X act(const X &x, const A &a, const ll &size) {
return {x.fi, x.se * a.fi + x.fi * a.se};
}
};
#line 2 "alg/monoid/add_pair.hpp"
template <typename E>
struct Monoid_Add_Pair {
using value_type = pair<E, E>;
using X = value_type;
static constexpr X op(const X &x, const X &y) {
return {x.fi + y.fi, x.se + y.se};
}
static constexpr X inverse(const X &x) { return {-x.fi, -x.se}; }
static constexpr X unit() { return {0, 0}; }
static constexpr bool commute = true;
};
#line 2 "alg/monoid/affine.hpp"
// op(F, G) = comp(G,F), F のあとで G
template <typename K>
struct Monoid_Affine {
using F = pair<K, K>;
using value_type = F;
using X = value_type;
static constexpr F op(const F &x, const F &y) noexcept {
return F({x.first * y.first, x.second * y.first + y.second});
}
static constexpr F inverse(const F &x) {
auto [a, b] = x;
a = K(1) / a;
return {a, a * (-b)};
}
static constexpr K eval(const F &f, K x) noexcept {
return f.first * x + f.second;
}
static constexpr F unit() { return {K(1), K(0)}; }
static constexpr bool commute = false;
};
#line 3 "alg/acted_monoid/cntsum_affine.hpp"
template <typename E>
struct ActedMonoid_CntSum_Affine {
using Monoid_X = Monoid_Add_Pair<E>;
using Monoid_A = Monoid_Affine<E>;
using X = typename Monoid_X::value_type;
using A = typename Monoid_A::value_type;
static constexpr X act(const X &x, const A &a, const ll &size) {
return {x.fi, x.se * a.fi + x.fi * a.se};
}
};