monoids/linear_function.hpp

• View this file on GitHub
• Last update: 2019-12-27 19:16:13+09:00
• Include: #include "monoids/linear_function.hpp"

Required by

• monoids/linear_function_plus_count_action.hpp

Verified with

• data_structure/lazy_propagation_red_black_tree.range_affine_range_sum.test.cpp
• data_structure/lazy_propagation_segment_tree.range_affine_range_sum.test.cpp
• data_structure/link_cut_tree.dynamic_tree_vertex_set_path_composite.test.cpp
• data_structure/link_cut_tree.vertex_set_path_composite.test.cpp
• data_structure/segment_tree.point_set_range_composite.test.cpp
• data_structure/sliding_window_aggregation.yosupo.test.cpp

Code

#pragma once
#include <utility>

template <class CommutativeRing>
struct linear_function_monoid {
    typedef std::pair<CommutativeRing, CommutativeRing> value_type;
    linear_function_monoid() = default;
    value_type unit() const {
        return std::make_pair(1, 0);
    }
    value_type mult(value_type g, value_type f) const {
        CommutativeRing fst = g.first * f.first;
        CommutativeRing snd = g.second + g.first * f.second;
        return std::make_pair(fst, snd);
    }
};

#line 2 "monoids/linear_function.hpp"
#include <utility>

template <class CommutativeRing>
struct linear_function_monoid {
    typedef std::pair<CommutativeRing, CommutativeRing> value_type;
    linear_function_monoid() = default;
    value_type unit() const {
        return std::make_pair(1, 0);
    }
    value_type mult(value_type g, value_type f) const {
        CommutativeRing fst = g.first * f.first;
        CommutativeRing snd = g.second + g.first * f.second;
        return std::make_pair(fst, snd);
    }
};

Back to top page