区間和・区間代入用のヘルパークラス (utility/action/set_sum.cpp)

#ifndef H_action_set_sum
#define H_action_set_sum

/**
 * @brief 区間和・区間代入用のヘルパークラス
 * @author えびちゃん
 */

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

template <typename Tp>
struct action_set_to_sum {
  using operand_type = length_monoid<Tp>;
  using action_type = set_monoid<Tp>;

  static void act(operand_type& op, action_type const& a) {
    if (a.empty()) return;
    op = operand_type(a.get() * op.length(), op.length());
  }
};

#endif  /* !defined(H_action_set_sum) */

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



/**
 * @brief 区間和・区間代入用のヘルパークラス
 * @author えびちゃん
 */

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

#include <cstddef>
#include <utility>

#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 1 "utility/monoid/set.cpp"



/**
 * @brief モノイドクラス
 * @author えびちゃん
 */

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

private:
  bool M_empty = true;
  value_type M_x;

public:
  set_monoid() = default;  // identity

  set_monoid(value_type const& x): M_empty(false), M_x(x) {}

  set_monoid& operator +=(set_monoid const& that) {
    M_empty = that.M_empty;
    if (!that.M_empty) M_x = that.M_x;
    return *this;
  }
  friend bool operator ==(set_monoid const& lhs, set_monoid const& rhs) {
    if (lhs.M_empty && rhs.M_empty) return true;
    if (lhs.M_empty != rhs.M_empty) return false;
    return lhs.M_x == rhs.M_x;
  }

  friend set_monoid operator +(set_monoid lhs, set_monoid const& rhs) { return lhs += rhs; }
  friend bool operator !=(set_monoid const& lhs, set_monoid const& rhs) {
    return !(lhs == rhs);
  }

  bool empty() const noexcept { return M_empty; }
  value_type const& get() const { return M_x; }
};


#line 11 "utility/action/set_sum.cpp"

template <typename Tp>
struct action_set_to_sum {
  using operand_type = length_monoid<Tp>;
  using action_type = set_monoid<Tp>;

  static void act(operand_type& op, action_type const& a) {
    if (a.empty()) return;
    op = operand_type(a.get() * op.length(), op.length());
  }
};