library/algebra/lazy/AddMin.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/algebra/lazy/AddMin.hpp"

Depends on

Verified with

Code

#pragma once
#include "library/algebra/group/Add.hpp"
#include "library/algebra/monoid/Min.hpp"
template <typename X> struct LazyAddMin {
    using MX = MonoidMin<X>;
    using MF = GroupAdd<X>;
    static constexpr X mapping(const X &f, const X &x) { return f + x; }
};

#line 2 "library/algebra/group/Add.hpp"
template<typename X>
struct GroupAdd {
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr void Rchop(X&x, const X&y){ x+=y; }
  static constexpr void Lchop(const X&x, X&y){ y+=x; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, long long n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 1 "library/algebra/monoid/Min.hpp"
template <typename X> struct MonoidMin {
    using value_type = X;
    static constexpr X op(const X &x, const X &y) noexcept {
        return std::min(x, y);
    }
    static constexpr void Rchop(X &x, const X &y) {
        if (x > y)
            x = y;
    }
    static constexpr void Lchop(const X &x, X &y) {
        if (y > x)
            y = x;
    }
    static constexpr X unit() { return std::numeric_limits<X>::max() / 2; }
    static constexpr bool commute = true;
};
#line 4 "library/algebra/lazy/AddMin.hpp"
template <typename X> struct LazyAddMin {
    using MX = MonoidMin<X>;
    using MF = GroupAdd<X>;
    static constexpr X mapping(const X &f, const X &x) { return f + x; }
};