traits/sum_affine_action.cpp

• View this file on GitHub
• Last update: 2021-12-28 21:38:32+09:00

Depends on

• traits/affine_composite_monoid.cpp
• traits/pair_monoid.cpp
• traits/sum_group.cpp

Verified with

• test/lazy_segment_tree.test.cpp

Code

#pragma once
#include "affine_composite_monoid.cpp"
#include "pair_monoid.cpp"
#include "sum_group.cpp"

template <class T> struct SumAffineAction {
    using Monoid = PairMonoid<SumGroup<T>, SumGroup<T>>;
    using Effector = AffineCompositeMonoid<T>;
    static constexpr std::pair<T, T> operation(const std::pair<T, T>& m, const Affine<T>& e) {
        return {e.a * m.first + e.b * m.second, m.second};
    }
};

#line 2 "traits/affine_composite_monoid.cpp"

template <class T> struct Affine {
    T a, b;
    constexpr Affine(const T& a = 1, const T& b = 0) : a(a), b(b) {}
    constexpr T eval(const T& x) const { return a * x + b; }
    constexpr Affine operator+(const Affine& other) const { return affine(a + other.a, b + other.b); }
    constexpr Affine composite(const Affine& other) const { return Affine(a * other.a, b * other.a + other.b); }
};

template <class T> struct AffineCompositeMonoid {
    using Type = Affine<T>;
    static constexpr Type identity() { return Type(); }
    static constexpr Type operation(const Type& l, const Type& r) noexcept { return l.composite(r); }
};
#line 2 "traits/pair_monoid.cpp"
#include <utility>

template <class M, class N> struct PairMonoid {
    using Type = std::pair<typename M::Type, typename N::Type>;
    static constexpr Type identity() { return {M::identity(), N::identity()}; }
    static constexpr Type operation(const Type& l, const Type& r) {
        return {M::operation(l.first, r.first), N::operation(l.second, r.second)};
    }
};
#line 2 "traits/sum_group.cpp"

template <class T> struct SumGroup {
    using Type = T;
    static constexpr T identity() { return T(0); }
    static constexpr T operation(const T& l, const T& r) { return l + r; }
    static constexpr T inverse(const T& x) { return -x; }
};
#line 5 "traits/sum_affine_action.cpp"

template <class T> struct SumAffineAction {
    using Monoid = PairMonoid<SumGroup<T>, SumGroup<T>>;
    using Effector = AffineCompositeMonoid<T>;
    static constexpr std::pair<T, T> operation(const std::pair<T, T>& m, const Affine<T>& e) {
        return {e.a * m.first + e.b * m.second, m.second};
    }
};

Back to top page