Convex Min Plus Convolution
(Convolution/convexminplus.hpp)

• View this file on GitHub
• Last update: 2024-01-17 06:35:27+09:00
• Include: #include "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

• Monotone Minima (Algorithm/monotoneminima.hpp)

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"

template<typename F>vector<int> MonotoneMinima(int R,int C,F cmp){
    // cmp(i,j,k) := compare A[i,j] and A[i,k] (A[i,j] -> false, A[i,k] -> true)

    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