monoids/reversible_monoid.hpp

• View this file on GitHub
• Last update: 2026-01-04 02:17:36+09:00
• Include: #include "monoids/reversible_monoid.hpp"

Verified with

• test/link_cut_tree/dynamic_tree_vertex_set_path_composite.test.cpp

Code

#ifndef REVERSIBLE_MONOID_HPP
#define REVERSIBLE_MONOID_HPP

template <typename M> struct ReversibleMonoid {
    ReversibleMonoid(M x) : val(x), rev(x) {}
    ReversibleMonoid(M x, M y) : val(x), rev(y) {}
    static ReversibleMonoid op(ReversibleMonoid l, ReversibleMonoid r) {
        return {M::op(l.val, r.val), M::op(r.rev, l.rev)};
    }
    static ReversibleMonoid e() { return {M::e(), M::e()}; }
    static ReversibleMonoid toggle(ReversibleMonoid x) { return {x.rev, x.val}; }
    M val, rev;
};

#endif // REVERSIBLE_MONOID_HPP

#line 1 "monoids/reversible_monoid.hpp"



template <typename M> struct ReversibleMonoid {
    ReversibleMonoid(M x) : val(x), rev(x) {}
    ReversibleMonoid(M x, M y) : val(x), rev(y) {}
    static ReversibleMonoid op(ReversibleMonoid l, ReversibleMonoid r) {
        return {M::op(l.val, r.val), M::op(r.rev, l.rev)};
    }
    static ReversibleMonoid e() { return {M::e(), M::e()}; }
    static ReversibleMonoid toggle(ReversibleMonoid x) { return {x.rev, x.val}; }
    M val, rev;
};

Back to top page