traits/affine_composite_monoid.cpp

• View this file on GitHub
• Last update: 2021-09-27 22:23:01+09:00

Required by

• traits/sum_affine_action.cpp

Verified with

• test/heavy_light_decomposition.test.cpp
• test/lazy_segment_tree.test.cpp
• test/queue_aggregation.test.cpp
• test/segment_tree.test.cpp

Code

#pragma once

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/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); }
};

Back to top page