test/yosupo/min_plus_convolution_convex_arbitrary.test.cpp

View this file on GitHub
Last update: 2024-04-25 15:52:43+09:00
Problem: https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary

Depends on

Code

#define PROBLEM \
    "https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary"

#include <bits/stdc++.h>

#include "../../convolution/convex_min_plus_convolution.hpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<long long> a(N), b(M);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    auto c = convex_min_plus_convolution(b, a);
    for (int i = 0; i < N + M - 1; ++i)
        cout << c[i] << (i < N + M - 2 ? " " : "\n");
}

#line 1 "test/yosupo/min_plus_convolution_convex_arbitrary.test.cpp"
#define PROBLEM \
    "https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary"

#include <bits/stdc++.h>

#line 3 "dp/monotone_minima.hpp"

template <typename F>
std::vector<int> monotone_minima(int n, int m, const F& f) {
    std::vector<int> idx(n, -1);

    auto calc = [&](const auto& calc, int l, int r, int optl,
                    int optr) -> void {
        if (l > r) return;
        int m = std::midpoint(l, r);
        auto mi = f(m, optl);
        idx[m] = optl;
        for (int i = optl + 1; i <= optr; ++i) {
            auto v = f(m, i);
            if (mi > v) {
                mi = v;
                idx[m] = i;
            }
        }
        calc(calc, l, m - 1, optl, idx[m]);
        calc(calc, m + 1, r, idx[m], optr);
    };

    calc(calc, 0, n - 1, 0, m - 1);
    return idx;
}
#line 5 "convolution/convex_min_plus_convolution.hpp"

// b is convex
template <typename T>
std::vector<T> convex_min_plus_convolution(const std::vector<T>& a,
                                           const std::vector<T>& b) {
    int len = a.size() + b.size() - 1;

    auto f = [&](int i, int j) {
        if (i - j < 0 || (int)b.size() <= i - j)
            return std::numeric_limits<T>::max();
        return a[j] + b[i - j];
    };

    auto idx = monotone_minima(len, a.size(), f);
    std::vector<T> res(len);
    for (int i = 0; i < len; ++i) res[i] = f(i, idx[i]);
    return res;
}

// b is concave
template <typename T>
std::vector<T> concave_max_plus_convolution(std::vector<T> a,
                                            std::vector<T> b) {
    for (auto& x : a) x = -x;
    for (auto& x : b) x = -x;
    auto c = convex_min_plus_convolution(a, b);
    for (auto& x : c) x = -x;
    return c;
}
#line 7 "test/yosupo/min_plus_convolution_convex_arbitrary.test.cpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<long long> a(N), b(M);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    auto c = convex_min_plus_convolution(b, a);
    for (int i = 0; i < N + M - 1; ++i)
        cout << c[i] << (i < N + M - 2 ? " " : "\n");
}