モノイド作用素
(library/various/monoid_act.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/various/monoid_act.hpp"

モノイド作用素

できること

• 二項演算を定義してるだけ

計算量

$O(1)$

使い方

LazySegmentTree<int, int> seg(Monoid::Min::op, Monoid::Min::e, Monoid::Add::op, Monoid::Add::e, MonoidAct::MinAdd::op N);

Depends on

• モノイド (library/various/monoid.hpp)

Required by

• Lazy Segment Tree (library/segtree/lazy_segment_tree.hpp)
• 統合セグ木 (library/segtree/unified_segment_tree.hpp)

Verified with

• 木 - HLDのテスト 木上クエリ:最大連続部分列和 (tests/graph.tree.heavy_light_decomposition.test.cpp)
• 遅延セグ木のテスト:RMQ RUQ (tests/segtree.lazy_segment_tree.test.cpp)
• 統合セグ木のテスト:RMQ RAQ (tests/segtree.unified_segment_tree.test.cpp)

Code

#pragma once
#include "library/various/monoid.hpp"
/**
 * @brief モノイド作用素
 */
struct MonoidAct {
    // 演算: 加算  更新: 加算
    struct AddAdd {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            return node + a * size;
        }
    };
    // 演算: 加算  更新: 代入
    struct AddSet {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            return a == Monoid::Set::e ? node : a * size;
        }
    };
    // 演算: 加算  更新: 最小値
    struct AddMin {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return min(node, a);
        }
    };
    // 演算: 加算  更新: 最大値
    struct AddMax {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return max(node, a);
        }
    };
    // 演算: 最小値  更新: 加算
    struct MinAdd {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return node == Monoid::Min::e ? node : node + a;
        }
    };
    // 演算: 最小値  更新: 代入
    struct MinSet {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return a == Monoid::Set::e ? node : a;
        }
    };
    // 演算: 最小値  更新: 最小値
    struct MinMin {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return min(node, a);
        }
    };
    // 演算: 最小値  更新: 最大値
    struct MinMax {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return max(node, a);
        }
    };
    // 演算: 最大値  更新: 加算
    struct MaxAdd {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return node == Monoid::Max::e ? node : node + a;
        }
    };
    // 演算: 最大値  更新: 代入
    struct MaxSet {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return a == Monoid::Set::e ? node : a;
        }
    };
    // 演算: 最大値  更新: 最小値
    struct MaxMin {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return min(node, a);
        }
    };
    // 演算: 最大値  更新: 最大値
    struct MaxMax {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return max(node, a);
        }
    };
};

#line 2 "library/various/monoid.hpp"
/**
 * @brief モノイド
 */
struct Monoid {
    // 最小値
    struct Min {
        static constexpr int e = INT_MAX;
        static int op(int x, int y) { return min(x, y); }
    };
    // 最大値
    struct Max {
        static constexpr int e = -INT_MAX;
        static int op(int x, int y) { return max(x, y); }
    };
    // 加算
    struct Add {
        static constexpr int e = 0;
        static int op(int x, int y) { return x + y; }
    };
    // 乗算
    struct Mul {
        static constexpr int e = 1;
        static int op(int x, int y) { return x * y; }
    };
    // 代入
    struct Set {
        static constexpr int e = INT_MAX;
        static int op(int x, int y) { return y == INT_MAX ? x : y; }
    };
    // 最大公約数
    struct Gcd {
        static constexpr int e = 0;
        static int op(int x, int y) { return gcd(x, y); }
    };
    // 最小公倍数
    struct Lcm {
        static constexpr int e = 1;
        static int op(int x, int y) { return lcm(x, y); }
    };
    // 排他的論理和
    struct Xor {
        static constexpr int e = 0;
        static int op(int x, int y) { return x ^ y; }
    };
};
#line 3 "library/various/monoid_act.hpp"
/**
 * @brief モノイド作用素
 */
struct MonoidAct {
    // 演算: 加算  更新: 加算
    struct AddAdd {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            return node + a * size;
        }
    };
    // 演算: 加算  更新: 代入
    struct AddSet {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            return a == Monoid::Set::e ? node : a * size;
        }
    };
    // 演算: 加算  更新: 最小値
    struct AddMin {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return min(node, a);
        }
    };
    // 演算: 加算  更新: 最大値
    struct AddMax {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return max(node, a);
        }
    };
    // 演算: 最小値  更新: 加算
    struct MinAdd {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return node == Monoid::Min::e ? node : node + a;
        }
    };
    // 演算: 最小値  更新: 代入
    struct MinSet {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return a == Monoid::Set::e ? node : a;
        }
    };
    // 演算: 最小値  更新: 最小値
    struct MinMin {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return min(node, a);
        }
    };
    // 演算: 最小値  更新: 最大値
    struct MinMax {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return max(node, a);
        }
    };
    // 演算: 最大値  更新: 加算
    struct MaxAdd {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return node == Monoid::Max::e ? node : node + a;
        }
    };
    // 演算: 最大値  更新: 代入
    struct MaxSet {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return a == Monoid::Set::e ? node : a;
        }
    };
    // 演算: 最大値  更新: 最小値
    struct MaxMin {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return min(node, a);
        }
    };
    // 演算: 最大値  更新: 最大値
    struct MaxMax {
        static constexpr int op(const int &node, const int &a,
                                const int &size) {
            (void)size; // unused
            return max(node, a);
        }
    };
};

Back to top page