dp/concave-min-plus-convolution.hpp

• View this file on GitHub
• Last update: 2024-04-28 09:13:11+09:00
• Include: #include "dp/concave-min-plus-convolution.hpp"

Depends on

• monotone minima (dp/monotone-minima.hpp)

Verified with

• verify/verify-yosupo-math/yosupo-concave-min-plus-convolution-1.test.cpp
• verify/verify-yosupo-math/yosupo-concave-min-plus-convolution-2.test.cpp

Code

#pragma once

#include <vector>
using namespace std;

#include "monotone-minima.hpp"

// a は下に凸, b は自由
template <typename T>
vector<T> concave_min_plus_convolution(const vector<T>& a, const vector<T>& b) {
  if (a.empty() or b.empty()) return {};
  int n = a.size(), m = b.size();
  auto argmin = monotone_minima(n + m - 1, m, [&](int i, int j, int k) {
    if (i < k) return true;
    if (i - j >= n) return false;
    return a[i - j] + b[j] <= a[i - k] + b[k];
  });
  vector<T> ans(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) {
    int j = argmin[i];
    ans[i] = a[i - j] + b[j];
  }
  return ans;
}

// a は上に凸, b は自由
template <typename T>
vector<T> concave_max_plus_convolution(const vector<T>& a, const vector<T>& b) {
  if (a.empty() or b.empty()) return {};
  int n = a.size(), m = b.size();
  auto argmin = monotone_minima(n + m - 1, m, [&](int i, int j, int k) {
    if (i < k) return true;
    if (i - j >= n) return false;
    return a[i - j] + b[j] >= a[i - k] + b[k];
  });
  vector<T> ans(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) {
    int j = argmin[i];
    ans[i] = a[i - j] + b[j];
  }
  return ans;
}

#line 2 "dp/concave-min-plus-convolution.hpp"

#include <vector>
using namespace std;

#line 2 "dp/monotone-minima.hpp"

#include <functional>
#line 5 "dp/monotone-minima.hpp"
using namespace std;

// NxN 行列がある
// m_i := argmin_j (A_{i,j}) が単調増加であるときに m_i を列挙する
// f(i, j, k) :
// A[i][j] と A[i][k] を比較 (j < k が保証されている)
// A[i][j] <= A[i][k] のとき true を返す関数を入れる (等号はどちらでもよい)
vector<int> monotone_minima(int N, int M,
                            const function<bool(int, int, int)>& f) {
  vector<int> res(N);
  auto dfs = [&](auto rc, int is, int ie, int l, int r) -> void {
    if (is == ie) return;
    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;
    rc(rc, is, i, l, m + 1);
    rc(rc, i + 1, ie, m, r);
  };
  dfs(dfs, 0, N, 0, M);
  return res;
}

// NxM 行列がある
// m_i := argmin_j (A_{i,j}) が単調増加であるときに m_i を列挙する
// A(i, j) : A[i][j] を返す関数
template <typename T>
vector<int> monotone_minima(int N, int M, const function<T(int, int)>& A) {
  function<bool(int, int, int)> f = [&](int i, int j, int k) -> bool {
    return A(i, j) <= A(i, k);
  };
  return monotone_minima(N, M, f);
}

/**
 * @brief monotone minima
 */
#line 7 "dp/concave-min-plus-convolution.hpp"

// a は下に凸, b は自由
template <typename T>
vector<T> concave_min_plus_convolution(const vector<T>& a, const vector<T>& b) {
  if (a.empty() or b.empty()) return {};
  int n = a.size(), m = b.size();
  auto argmin = monotone_minima(n + m - 1, m, [&](int i, int j, int k) {
    if (i < k) return true;
    if (i - j >= n) return false;
    return a[i - j] + b[j] <= a[i - k] + b[k];
  });
  vector<T> ans(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) {
    int j = argmin[i];
    ans[i] = a[i - j] + b[j];
  }
  return ans;
}

// a は上に凸, b は自由
template <typename T>
vector<T> concave_max_plus_convolution(const vector<T>& a, const vector<T>& b) {
  if (a.empty() or b.empty()) return {};
  int n = a.size(), m = b.size();
  auto argmin = monotone_minima(n + m - 1, m, [&](int i, int j, int k) {
    if (i < k) return true;
    if (i - j >= n) return false;
    return a[i - j] + b[j] >= a[i - k] + b[k];
  });
  vector<T> ans(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) {
    int j = argmin[i];
    ans[i] = a[i - j] + b[j];
  }
  return ans;
}

Back to top page