区間 Affine 変換・区間加算用のヘルパークラス (utility/action/affine_sum.cpp)

#ifndef H_action_affine_sum
#define H_action_affine_sum

/**
 * @brief 区間 Affine 変換・区間加算用のヘルパークラス
 * @author えびちゃん
 */

#include "utility/monoid/composite.cpp"
#include "utility/monoid/length.cpp"

#include <utility>

template <typename Tp>
struct action_affine_to_sum {
  using operand_type = length_monoid<Tp>;
  using action_type = composite_monoid<Tp>;

  static void act(operand_type& op, action_type const& f) {
    auto [a, b] = f.get();
    op = operand_type(a * op.get() + op.length() * b, op.length());
  }
};

#endif  /* !defined(H_action_affine_sum) */

#line 1 "utility/action/affine_sum.cpp"



/**
 * @brief 区間 Affine 変換・区間加算用のヘルパークラス
 * @author えびちゃん
 */

#line 1 "utility/monoid/composite.cpp"
/**
 * @brief 一次関数の合成を得る演算のモノイド
 * @author えびちゃん
 */

#include <algorithm>
#include <utility>

#ifndef H_composite_monoid
#define H_composite_monoid

template <typename Tp>
class composite_monoid {
public:
  using value_type = Tp;

private:
  value_type M_a = 1;
  value_type M_b = 0;

public:
  composite_monoid() = default;  // identity

  composite_monoid(value_type a, value_type b): M_a(a), M_b(b) {};

  composite_monoid& operator +=(composite_monoid that) {
    M_a *= that.M_a;
    M_b *= that.M_a;
    M_b += that.M_b;
    return *this;
  }

  composite_monoid operator +(composite_monoid const& that) const {
    return composite_monoid(*this) += that;
  }
  composite_monoid operator +(composite_monoid&& that) const {
    return composite_monoid(*this) += std::move(that);
  }

  bool operator ==(composite_monoid const& that) const {
    return (M_a == that.M_a && M_b == that.M_b);
  }
  bool operator !=(composite_monoid const& that) const { return !(*this == that); }

  auto get() const { return std::make_pair(M_a, M_b); }
  value_type operator ()(value_type x) const { return M_a * x + M_b; }
};

#endif  /* !defined(H_composite_monoid) */
#line 1 "utility/monoid/length.cpp"
/**
 * @brief 和と長さを得る演算のモノイド
 * @author えびちゃん
 */

#include <cstddef>
#line 8 "utility/monoid/length.cpp"

#ifndef H_length_monoid
#define H_length_monoid

template <typename Tp>
class length_monoid {
public:
  using value_type = Tp;
  using size_type = size_t;

private:
  value_type M_x{};
  size_type M_l = 1;

public:
  length_monoid() = default;  // identity

  length_monoid(value_type const& x, size_type l = 1): M_x(x), M_l(l) {};
  length_monoid(value_type&& x, size_type l = 1): M_x(std::move(x)), M_l(l) {};

  length_monoid& operator +=(length_monoid const& that) {
    M_x += that.M_x;
    M_l += that.M_l;
    return *this;
  }
  length_monoid& operator +=(length_monoid&& that) {
    M_x += std::move(that.M_x);
    M_l += that.M_l;
    return *this;
  }

  length_monoid operator +(length_monoid const& that) const {
    return length_monoid(*this) += that;
  }
  length_monoid operator +(length_monoid&& that) const {
    return length_monoid(*this) += std::move(that);
  }

  value_type const& get() const { return M_x; }
  size_type length() const { return M_l; }
};

#endif  /* !defined(H_length_monoid) */
#line 11 "utility/action/affine_sum.cpp"

#line 13 "utility/action/affine_sum.cpp"

template <typename Tp>
struct action_affine_to_sum {
  using operand_type = length_monoid<Tp>;
  using action_type = composite_monoid<Tp>;

  static void act(operand_type& op, action_type const& f) {
    auto [a, b] = f.get();
    op = operand_type(a * op.get() + op.length() * b, op.length());
  }
};