alg/acted_monoid/sum_affine.hpp

• View this file on GitHub
• Last update: 2024-01-23 05:58:02+09:00
• Include: #include "alg/acted_monoid/sum_affine.hpp"

Depends on

• alg/monoid/add.hpp
• alg/monoid/affine.hpp

Verified with

• test/2_library_checker/data_structure/dynamic_sequence_range_affine_range_sum_rbst.test.cpp
• test/2_library_checker/data_structure/dynamic_sequence_range_affine_range_sum_splay.test.cpp
• test/2_library_checker/data_structure/range_affine_range_sum.test.cpp
• test/3_yukicoder/2342.test.cpp

Code

#include "alg/monoid/add.hpp"

#include "alg/monoid/affine.hpp"


template <typename E>
struct ActedMonoid_Sum_Affine {
  using Monoid_X = Monoid_Add<E>;
  using Monoid_A = Monoid_Affine<E>;
  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) {
    return x * a.fi + E(size) * a.se;
  }
};

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

template <typename E>
struct Monoid_Add {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 2 "alg/monoid/affine.hpp"

// op(F, G) = comp(G,F), F のあとで G
template <typename K>
struct Monoid_Affine {
  using F = pair<K, K>;
  using value_type = F;
  using X = value_type;
  static constexpr F op(const F &x, const F &y) noexcept {
    return F({x.first * y.first, x.second * y.first + y.second});
  }
  static constexpr F inverse(const F &x) {
    auto [a, b] = x;
    a = K(1) / a;
    return {a, a * (-b)};
  }
  static constexpr K eval(const F &f, K x) noexcept {
    return f.first * x + f.second;
  }
  static constexpr F unit() { return {K(1), K(0)}; }
  static constexpr bool commute = false;
};
#line 3 "alg/acted_monoid/sum_affine.hpp"

template <typename E>
struct ActedMonoid_Sum_Affine {
  using Monoid_X = Monoid_Add<E>;
  using Monoid_A = Monoid_Affine<E>;
  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) {
    return x * a.fi + E(size) * a.se;
  }
};

Back to top page