Set Operator
(Src/Algebra/Action/SetOperator.hpp)

• View this file on GitHub
• Last update: 2026-01-14 16:33:38+09:00
• Include: #include "Src/Algebra/Action/SetOperator.hpp"

example

struct OP {
    using Element = long long;
    static Element identity() {
        return 0;
    }
    static void add(Element& s, int v) {
        s += v;
    }
    static void remove(Element& s, int v) {
        s -= v;
    }
};

remove(s, v)の前には(まだremoveされていない)add(s, v)と丁度一つ対応させることができる時に使う。

Required by

• 要素昇順 $K$ 個、降順 $N - K$ 個の総積を管理 (Src/DataStructure/Heap/PartitionedProducts.hpp)
• グレイコードによる部分集合列挙 (Src/Utility/GreyCode.hpp)

Verified with

• Test/AtCoder/abc306_e.test.cpp
• Test/AtCoder/abc440_f.test.cpp
• Test/AtCoder/arc196_a.test.cpp
• Test/CF/CF1070-F.test.cpp

Code

#pragma once

#include <concepts>

namespace zawa {

namespace concepts {

template <class S, class T>
concept SetOperator = requires {
    typename S::Element;
    { S::identity() } -> std::same_as<typename S::Element>;
    { S::add(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
    { S::remove(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
};

} // namespace concepts

} // namespace zawa

#line 2 "Src/Algebra/Action/SetOperator.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class S, class T>
concept SetOperator = requires {
    typename S::Element;
    { S::identity() } -> std::same_as<typename S::Element>;
    { S::add(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
    { S::remove(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
};

} // namespace concepts

} // namespace zawa

Back to top page