alg/monoid/affine.hpp

• View this file on GitHub
• Last update: 2023-07-25 22:13:04+09:00
• Include: #include "alg/monoid/affine.hpp"
• Link: View error logs on GitHub Actions

Required by

• alg/acted_monoid/cntsum_affine.hpp
• alg/acted_monoid/sum_affine.hpp
• alg/acted_set/affine.hpp

Verified with

• test/1_mytest/mo_on_tree.test.cpp
• test/1_mytest/prefix_max_segtree.test.cpp
• test/1_mytest/rbst_monoid_2.test.cpp
• test/1_mytest/splay.test.cpp
• test/2_library_checker/data_structure/deque_operate_all_compsite.test.cpp
• test/2_library_checker/data_structure/dynamic_point_rectangle_affine_rectangle_sum.test.cpp
• 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/point_set_range_composite_dynamic.test.cpp
• test/2_library_checker/data_structure/point_set_range_composite_monoid.test.cpp
• test/2_library_checker/data_structure/queue_operate_all_composite.test.cpp
• test/2_library_checker/data_structure/range_affine_point_add.test.cpp
• test/2_library_checker/data_structure/range_affine_range_sum.test.cpp
• test/2_library_checker/data_structure/range_set_range_composite.test.cpp
• test/2_library_checker/data_structure/sort_segtree.test.cpp
• test/2_library_checker/data_structure/sort_segtree_1.test.cpp
• test/2_library_checker/tree/dynamic_tree_vertex_set_path_composite.test.cpp
• test/2_library_checker/tree/vertex_set_path_composite_monoid.test.cpp
• test/3_yukicoder/1502.test.cpp
• test/3_yukicoder/1891.test.cpp
• test/3_yukicoder/2342.test.cpp
• test/3_yukicoder/2342_2.test.cpp
• test/3_yukicoder/255.test.cpp
• test/3_yukicoder/2595.test.cpp
• test/5_atcoder/abc222g.test.cpp
• test/5_atcoder/abc270_g.test.cpp

Code

#pragma once

// 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 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;
};

Back to top page