alg/acted_monoid/summin_assign.hpp

View this file on GitHub
Last update: 2023-10-14 20:28:40+09:00
Include: #include "alg/acted_monoid/summin_assign.hpp"

Depends on

Verified with

test/mytest/summin_assign.test.cpp

Code

#include "alg/monoid/summin.hpp"
#include "alg/monoid/assign.hpp"

template <typename E, ll none_val>
struct ActedMonoid_CntSumMin_Assign {
  using Monoid_X = Monoid_SumMin<E>;
  using Monoid_A = Monoid_Assign<ll, none_val>;
  using X = typename Monoid_X::value_type;
  using A = typename Monoid_A::value_type;
  static constexpr X act(const X& x, const A& a, const ll& size) {
    if (a == Monoid_A::unit()) return x;
    return {E(size) * a, a};
  }
};

#line 2 "alg/monoid/summin.hpp"

template <typename E>
struct Monoid_SumMin {
  using value_type = pair<E, E>;
  using X = value_type;
  static X op(X x, X y) { return {x.fi + y.fi, min(x.se, y.se)}; }
  static X from_element(E x) { return {x, x}; }
  static constexpr X unit() { return {E(0), infty<E>}; }
  static constexpr bool commute = true;
};
#line 2 "alg/monoid/assign.hpp"

template <typename X, int none_val>
struct Monoid_Assign {
  using value_type = X;
  static X op(X x, X y) { return (y == X(none_val) ? x : y); }
  static constexpr X unit() { return X(none_val); }
  static constexpr bool commute = false;
};
#line 3 "alg/acted_monoid/summin_assign.hpp"

template <typename E, ll none_val>
struct ActedMonoid_CntSumMin_Assign {
  using Monoid_X = Monoid_SumMin<E>;
  using Monoid_A = Monoid_Assign<ll, none_val>;
  using X = typename Monoid_X::value_type;
  using A = typename Monoid_A::value_type;
  static constexpr X act(const X& x, const A& a, const ll& size) {
    if (a == Monoid_A::unit()) return x;
    return {E(size) * a, a};
  }
};