structure/class/range-affine-range-sum.hpp

View this file on GitHub
Last update: 2024-08-10 03:11:07+09:00
Include: #include "structure/class/range-affine-range-sum.hpp"

Depends on

structure/class/affine.hpp

Verified with

test/verify/yosupo-range-affine-range-sum.test.cpp

Code

#include "affine.hpp"

template <typename T>
struct RangeAffineRangeSum {
  using S = pair<T, T>;
  using F = Affine<T>;
  static constexpr S op(const S &a, const S &b) {
    return {a.first + b.first, a.second + b.second};
  }
  static constexpr S e() { return {0, 0}; }
  static constexpr S mapping(const S &x, const F &f) {
    return {x.first * f.a + x.second * f.b, x.second};
  }
  static constexpr F composition(const F &f, const F &g) { return F::op(f, g); }
  static constexpr F id() { return F(); }
};

#line 1 "structure/class/affine.hpp"
template <typename T>
struct Affine {
  T a, b;  // ax+b
  Affine() : a(1), b(0) {}
  Affine(T a, T b) : a(a), b(b) {}
  T eval(T x) const { return a * x + b; }
  static constexpr Affine op(const Affine& l, const Affine& r) {
    return {l.a * r.a, l.b * r.a + r.b};
  }
  constexpr bool operator==(const Affine& p) const {
    return a == p.a and b == p.b;
  }
  constexpr bool operator!=(const Affine& p) const {
    return a != p.a or b != p.b;
  }
};
#line 2 "structure/class/range-affine-range-sum.hpp"

template <typename T>
struct RangeAffineRangeSum {
  using S = pair<T, T>;
  using F = Affine<T>;
  static constexpr S op(const S &a, const S &b) {
    return {a.first + b.first, a.second + b.second};
  }
  static constexpr S e() { return {0, 0}; }
  static constexpr S mapping(const S &x, const F &f) {
    return {x.first * f.a + x.second * f.b, x.second};
  }
  static constexpr F composition(const F &f, const F &g) { return F::op(f, g); }
  static constexpr F id() { return F(); }
};