min_plus_convolution
(src/convolution/min_plus_convolution.hpp)

View this file on GitHub
Last update: 2025-07-24 17:37:03+09:00
Include: #include "src/convolution/min_plus_convolution.hpp"

min_plus_convolution

vector<T> min_plus_convolution(vector<T> a, vector<T> b)

長さ $n$ の下に凸な数列 $a$ と，長さ $m$ の任意の数列 $b$ から，長さ $n+m-1$の数列

\[c_i = \min_{j}\{a_{i-j} + b_{j}\}\]

を計算します．

制約

$a$ は下に凸

計算量

$O((n + m) \log n)$

max_plus_convolution

vector<T> max_plus_convolution(vector<T> a, vector<T> b)

長さ $n$ の上に凸な数列 $a$ と，長さ $m$ の任意の数列 $b$ から，長さ $n+m-1$の数列

\[c_i = \max_{j}\{a_{i-j} + b_{j}\}\]

を計算します．

制約

$a$ は上に凸

計算量

$O((n + m) \log n)$

Depends on

Verified with

Code

#pragma once
#include "../template/template.hpp"
#include "../dp/monotone_minima.hpp"
template <typename T>
vector<T> min_plus_convolution(const vector<T>& a, const vector<T>& b) {
    if(a.empty() or b.empty()) return {};
    const int n = a.size(), m = b.size();
    auto f = [&](const int i, const int j, const int k) -> bool {
        if(i < k) return true;
        if(i - j >= n) return false;
        return a[i - j] + b[j] < a[i - k] + b[k];
    };
    const auto argmin = monotone_minima(n + m - 1, m, f);
    vector<T> res(n + m - 1);
    for(int i = 0; i < n + m - 1; ++i) {
        const int j = argmin[i];
        res[i] = a[i - j] + b[j];
    }
    return res;
}
template <typename T>
vector<T> max_plus_convolution(const vector<T>& a, const vector<T>& b) {
    if(a.empty() or b.empty()) return {};
    const int n = a.size(), m = b.size();
    auto f = [&](const int i, const int j, const int k) -> bool {
        if(i < k) return true;
        if(i - j >= n) return false;
        return a[i - j] + b[j] > a[i - k] + b[k];
    };
    const auto argmax = monotone_minima(n + m - 1, m, f);
    vector<T> res(n + m - 1);
    for(int i = 0; i < n + m - 1; ++i) {
        const int j = argmax[i];
        res[i] = a[i - j] + b[j];
    }
    return res;
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/dp/monotone_minima.hpp"
template <class F>
vector<int> monotone_minima(const int n, const int m, const F& f) {
    vector<int> res(n);
    auto dfs = [&](const auto& dfs, const int is, const int ie, const int l, const int r) -> void {
        if(is == ie) return;
        const int i = (is + ie) / 2;
        int m = l;
        for(int k = l + 1; k < r; ++k) {
            if(!f(i, m, k)) m = k;
        }
        res[i] = m;
        dfs(dfs, is, i, l, m + 1);
        dfs(dfs, i + 1, ie, m, r);
    };
    dfs(dfs, 0, n, 0, m);
    return res;
}
#line 4 "src/convolution/min_plus_convolution.hpp"
template <typename T>
vector<T> min_plus_convolution(const vector<T>& a, const vector<T>& b) {
    if(a.empty() or b.empty()) return {};
    const int n = a.size(), m = b.size();
    auto f = [&](const int i, const int j, const int k) -> bool {
        if(i < k) return true;
        if(i - j >= n) return false;
        return a[i - j] + b[j] < a[i - k] + b[k];
    };
    const auto argmin = monotone_minima(n + m - 1, m, f);
    vector<T> res(n + m - 1);
    for(int i = 0; i < n + m - 1; ++i) {
        const int j = argmin[i];
        res[i] = a[i - j] + b[j];
    }
    return res;
}
template <typename T>
vector<T> max_plus_convolution(const vector<T>& a, const vector<T>& b) {
    if(a.empty() or b.empty()) return {};
    const int n = a.size(), m = b.size();
    auto f = [&](const int i, const int j, const int k) -> bool {
        if(i < k) return true;
        if(i - j >= n) return false;
        return a[i - j] + b[j] > a[i - k] + b[k];
    };
    const auto argmax = monotone_minima(n + m - 1, m, f);
    vector<T> res(n + m - 1);
    for(int i = 0; i < n + m - 1; ++i) {
        const int j = argmax[i];
        res[i] = a[i - j] + b[j];
    }
    return res;
}