min-plus畳み込み(Min-Plus Convolution)
(math/min_plus_convolution.cpp)

• View this file on GitHub
• Last update: 2026-03-12 00:49:33+09:00

説明

c[k] = min_i (a[i] + b[k - i]) を計算する。 配列の凸性に応じて 3 種類の関数を使い分ける。

ここで凸とは、隣接差分が単調非減少であることを指す。

できること

• vector<T> min_plus_convolution_arbitrary_convex(const vector<T>& a, const vector<T>& b) a を任意列、b を凸列として min-plus 畳み込みを返す。計算量は $O((N + M) log(N + M))$
• vector<T> min_plus_convolution_convex_arbitrary(const vector<T>& a, const vector<T>& b) a を凸列、b を任意列として min-plus 畳み込みを返す。計算量は $O((N + M) log(N + M))$
• vector<T> min_plus_convolution_convex_convex(const vector<T>& a, const vector<T>& b) a, b を凸列として min-plus 畳み込みを返す。計算量は $O(N + M)$

使い方

凸性がある側に応じて関数を選ぶ。 返り値の長さは常に a.size() + b.size() - 1。

T は + と < が使える型を想定する。 空配列を渡したときは空配列を返す。

Verified with

• test/yosupo_min_plus_convolution_arbitrary_convex.test.cpp
• test/yosupo_min_plus_convolution_convex_arbitrary.test.cpp
• test/yosupo_min_plus_convolution_convex_convex.test.cpp

Code

using namespace std;

template<class T, class F>
vector<T> min_plus_convolution_monotone(int n, int m, F f) {
    vector<T> res(n + m - 1);
    auto dfs = [&](auto &&self, int left, int right, int opt_left, int opt_right) -> void {
        if (left > right) return;
        int mid = (left + right) >> 1;
        int from = max(opt_left, max(0, mid - (m - 1)));
        int to = min(opt_right, min(n - 1, mid));
        int best = from;
        T best_value = f(mid, from);
        for (int i = from + 1; i <= to; ++i) {
            T value = f(mid, i);
            if (value < best_value) {
                best = i;
                best_value = value;
            }
        }
        res[mid] = best_value;
        self(self, left, mid - 1, opt_left, best);
        self(self, mid + 1, right, best, opt_right);
    };
    dfs(dfs, 0, n + m - 2, 0, n - 1);
    return res;
}

template<class T>
vector<T> min_plus_convolution_arbitrary_convex(const vector<T> &a, const vector<T> &b) {
    if (a.empty() || b.empty()) return {};
    int n = a.size(), m = b.size();
    return min_plus_convolution_monotone<T>(n, m, [&](int k, int i) {
        return a[i] + b[k - i];
    });
}

template<class T>
vector<T> min_plus_convolution_convex_arbitrary(const vector<T> &a, const vector<T> &b) {
    if (a.empty() || b.empty()) return {};
    vector<T> ra(a.rbegin(), a.rend());
    vector<T> rb(b.rbegin(), b.rend());
    auto res = min_plus_convolution_arbitrary_convex(rb, ra);
    reverse(res.begin(), res.end());
    return res;
}

template<class T>
vector<T> min_plus_convolution_convex_convex(const vector<T> &a, const vector<T> &b) {
    if (a.empty() || b.empty()) return {};
    int n = a.size(), m = b.size();
    vector<T> res(n + m - 1);
    int i = 0, j = 0;
    res[0] = a[0] + b[0];
    for (int k = 1; k < n + m - 1; ++k) {
        if (i == n - 1) {
            ++j;
        } else if (j == m - 1) {
            ++i;
        } else if (a[i + 1] + b[j] < a[i] + b[j + 1]) {
            ++i;
        } else {
            ++j;
        }
        res[k] = a[i] + b[j];
    }
    return res;
}

/**
 * @brief min-plus畳み込み(Min-Plus Convolution)
 */

#line 1 "math/min_plus_convolution.cpp"
using namespace std;

template<class T, class F>
vector<T> min_plus_convolution_monotone(int n, int m, F f) {
    vector<T> res(n + m - 1);
    auto dfs = [&](auto &&self, int left, int right, int opt_left, int opt_right) -> void {
        if (left > right) return;
        int mid = (left + right) >> 1;
        int from = max(opt_left, max(0, mid - (m - 1)));
        int to = min(opt_right, min(n - 1, mid));
        int best = from;
        T best_value = f(mid, from);
        for (int i = from + 1; i <= to; ++i) {
            T value = f(mid, i);
            if (value < best_value) {
                best = i;
                best_value = value;
            }
        }
        res[mid] = best_value;
        self(self, left, mid - 1, opt_left, best);
        self(self, mid + 1, right, best, opt_right);
    };
    dfs(dfs, 0, n + m - 2, 0, n - 1);
    return res;
}

template<class T>
vector<T> min_plus_convolution_arbitrary_convex(const vector<T> &a, const vector<T> &b) {
    if (a.empty() || b.empty()) return {};
    int n = a.size(), m = b.size();
    return min_plus_convolution_monotone<T>(n, m, [&](int k, int i) {
        return a[i] + b[k - i];
    });
}

template<class T>
vector<T> min_plus_convolution_convex_arbitrary(const vector<T> &a, const vector<T> &b) {
    if (a.empty() || b.empty()) return {};
    vector<T> ra(a.rbegin(), a.rend());
    vector<T> rb(b.rbegin(), b.rend());
    auto res = min_plus_convolution_arbitrary_convex(rb, ra);
    reverse(res.begin(), res.end());
    return res;
}

template<class T>
vector<T> min_plus_convolution_convex_convex(const vector<T> &a, const vector<T> &b) {
    if (a.empty() || b.empty()) return {};
    int n = a.size(), m = b.size();
    vector<T> res(n + m - 1);
    int i = 0, j = 0;
    res[0] = a[0] + b[0];
    for (int k = 1; k < n + m - 1; ++k) {
        if (i == n - 1) {
            ++j;
        } else if (j == m - 1) {
            ++i;
        } else if (a[i + 1] + b[j] < a[i] + b[j + 1]) {
            ++i;
        } else {
            ++j;
        }
        res[k] = a[i] + b[j];
    }
    return res;
}

/**
 * @brief min-plus畳み込み(Min-Plus Convolution)
 */

Back to top page