マージテク
(library/sequence/merge.hpp)

• View this file on GitHub
• Last update: 2026-01-07 21:05:45+09:00
• Include: #include "library/sequence/merge.hpp"

マージテク

できること

• AをBにマージする
• Aは空にする

計算量

• vector: $O(NlogN)$
• set: $O(Nlog^2N)$

使い方

merge(A, B);
merge(stA, stB);
merge(mpA, mpB, [&](map<int, int> &B, pair<int, int> a){
    auto [k, v] = a;
    B[k] += v;
});

Verified with

• マージテクのテスト (tests/sequence.merge.test.cpp)

Code

#pragma once
template <typename T> void merge(vector<T> &A, vector<T> &B) {
    if (A.size() > B.size()) swap(A, B);
    for (auto &&v : A) B.push_back(v);
    A.clear();
}
template <typename T> void merge(set<T> &A, set<T> &B) {
    if (A.size() > B.size()) swap(A, B);
    for (auto &&v : A) B.insert(v);
    A.clear();
}
template <typename T, typename F> void merge(T &A, T &B, F f) {
    if (A.size() > B.size()) swap(A, B);
    for (auto &&v : A) {
        f(B, v);
    }
    A.clear();
}

#line 2 "library/sequence/merge.hpp"
template <typename T> void merge(vector<T> &A, vector<T> &B) {
    if (A.size() > B.size()) swap(A, B);
    for (auto &&v : A) B.push_back(v);
    A.clear();
}
template <typename T> void merge(set<T> &A, set<T> &B) {
    if (A.size() > B.size()) swap(A, B);
    for (auto &&v : A) B.insert(v);
    A.clear();
}
template <typename T, typename F> void merge(T &A, T &B, F f) {
    if (A.size() > B.size()) swap(A, B);
    for (auto &&v : A) {
        f(B, v);
    }
    A.clear();
}

Back to top page