monoids/left_action.hpp

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

Depends on

• monoids/left.hpp

Code

#pragma once
#include <utility>
#include "monoids/left.hpp"

/**
 * @note lazy_propagation_segment_tree<left_monoid<typename Monoid::value_type>, Monoid, left_action<Monoid> > is the same to dual_segment_tree<Monoid>
 */
template <class Monoid>
struct left_action {
    typename left_monoid<typename Monoid::value_type>::value_type operator () (typename Monoid::value_type f, typename left_monoid<typename Monoid::value_type>::value_type x) const {
        return x.first ? std::make_pair(true, Monoid().mult(f, x.second)) : x;
    }
};

#line 2 "monoids/left_action.hpp"
#include <utility>
#line 3 "monoids/left.hpp"

template <class T>
struct left_monoid {
    // typedef std::optional<T> value_type;
    typedef std::pair<bool, T> value_type;
    value_type unit() const { return std::make_pair(false, T()); }
    value_type mult(value_type a, value_type b) const { return a.first ? a : b; }
};
#line 4 "monoids/left_action.hpp"

/**
 * @note lazy_propagation_segment_tree<left_monoid<typename Monoid::value_type>, Monoid, left_action<Monoid> > is the same to dual_segment_tree<Monoid>
 */
template <class Monoid>
struct left_action {
    typename left_monoid<typename Monoid::value_type>::value_type operator () (typename Monoid::value_type f, typename left_monoid<typename Monoid::value_type>::value_type x) const {
        return x.first ? std::make_pair(true, Monoid().mult(f, x.second)) : x;
    }
};

Back to top page