library

This documentation is automatically generated by online-judge-tools/verification-helper

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

:warning: Convex Min Plus Convolution
(Convolution/convexminplus.hpp)

使い方

vector<T> ConvexMinPlusConvolution(vector<T>& a,vector<T>& b): $b$ は凸性 ($\forall i,b_i-b_{i-1} \leq b_{i+1}-b_i$) を満たすとする。
$c[n]=\min_{0 \leq k \leq n}a[k]+b[n-k]$ を計算。

Depends on

Code

#pragma once
#include "Algorithm/monotoneminima.hpp"


template <typename T>
vector<T> MinPlusConvolution_arbitrary_convex(vector<T> &a, vector<T> &b) {
    int n = a.size(), m = b.size();
    auto cmp = [&](int i, int j, int k) -> bool {
        if (i < k)
            return false;
        if (i - j >= m)
            return true;
        return a[j] + b[i - j] >= a[k] + b[i - k];
    };
    auto arg = MonotoneMinima(n + m - 1, n, cmp);
    vector<ll> ret(n + m - 1);
    rep(i, 0, n + m - 1) ret[i] = a[arg[i]] + b[i - arg[i]];
    return ret;
}

template <typename T>
vector<T> MinPlusConvolution_convex_convex(vector<T> &a, vector<T> &b) {
    int n = SZ(a), m = SZ(b);
    vector<T> c(n + m - 1);
    c[0] = a[0] + b[0];
    for (int k = 0, i = 0; k < n + m - 2; k++) {
        int j = k - i;
        if (j == m - 1 or (i < n - 1 and a[i + 1] + b[j] < a[i] + b[j + 1])) {
            c[k + 1] = a[++i] + b[j];
        } else {
            c[k + 1] = a[i] + b[++j];
        }
    }
    return c;
}

/**
 * @brief Convex Min Plus Convolution
 * @docs docs/convexminplus.md
 */
#line 2 "Algorithm/monotoneminima.hpp"

// cmp(i,j,k) := compare A[i,j] and A[i,k] (A[i,j] -> false, A[i,k] -> true)

template <typename F> vector<int> MonotoneMinima(int R, int C, F cmp) {
    vector<int> ret(R);
    auto rec = [&](auto &f, vector<int> target) -> void {
        int m = target.size();
        if (m == 0)
            return;
        vector<int> even;
        for (int i = 1; i < m; i += 2)
            even.push_back(target[i]);
        f(f, even);
        int cur = 0;
        for (int i = 0; i < m; i += 2) {
            ret[target[i]] = cur;
            int end = C - 1;
            if (i != m - 1)
                end = ret[even[i / 2]];
            while (cur < end) {
                cur++;
                if (cmp(target[i], ret[target[i]], cur))
                    ret[target[i]] = cur;
            }
        }
    };
    vector<int> tmp(R);
    iota(ALL(tmp), 0);
    rec(rec, tmp);
    return ret;
}

/**
 * @brief Monotone Minima
 * @docs docs/monotoneminima.md
 */
#line 3 "Convolution/convexminplus.hpp"

template <typename T>
vector<T> MinPlusConvolution_arbitrary_convex(vector<T> &a, vector<T> &b) {
    int n = a.size(), m = b.size();
    auto cmp = [&](int i, int j, int k) -> bool {
        if (i < k)
            return false;
        if (i - j >= m)
            return true;
        return a[j] + b[i - j] >= a[k] + b[i - k];
    };
    auto arg = MonotoneMinima(n + m - 1, n, cmp);
    vector<ll> ret(n + m - 1);
    rep(i, 0, n + m - 1) ret[i] = a[arg[i]] + b[i - arg[i]];
    return ret;
}

template <typename T>
vector<T> MinPlusConvolution_convex_convex(vector<T> &a, vector<T> &b) {
    int n = SZ(a), m = SZ(b);
    vector<T> c(n + m - 1);
    c[0] = a[0] + b[0];
    for (int k = 0, i = 0; k < n + m - 2; k++) {
        int j = k - i;
        if (j == m - 1 or (i < n - 1 and a[i + 1] + b[j] < a[i] + b[j + 1])) {
            c[k + 1] = a[++i] + b[j];
        } else {
            c[k + 1] = a[i] + b[++j];
        }
    }
    return c;
}

/**
 * @brief Convex Min Plus Convolution
 * @docs docs/convexminplus.md
 */
Back to top page