Library

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

View the Project on GitHub noshi91/Library

:heavy_check_mark: Concave Max Plus Convolution
(algorithm/concave_max_plus_convolution.cpp)

入力

長さ $N$ の列 $A$
長さ $M$ の列 $B$

出力

$C_i \mathrel := \max \limits _ j \lbrace A _ j + B _ {i - j} \rbrace$

で定義される長さ $N + M - 1$ の列 $C$

計算量

説明

$( N + M - 1 ) \times N$ 行列 $X$ を以下のように定義する。

$X _ {i , j} \mathrel := A _ j + B _ {i - j}$

ただし、$k \lt 0$ や $M \leq k$ に対する $B _ k$ は、十分小さい値を $B$ の凸性を保つように設定するものとする。
目的は $C _ i = \max \limits _ j X _ {i , j}$ を計算することである。
$B$ が上に凸であることから $X$ は (anti-)monge であり、すなわち totally monotone。よってSMAWK Algorithm を用いると $\Theta ( N + M )$ で計算可能。

文献

Depends on

Required by

Verified with

Code

#include "algorithm/smawk.cpp"
#include "other/int_alias.cpp"

#include <vector>

template <class T>
std::vector<T> concave_max_plus_convolution(const std::vector<T> &a,
                                            const std::vector<T> &b) {
  const usize n = a.size();
  const usize m = b.size();
  const auto get = [&](const usize i, const usize j) {
    return a[j] + b[i - j];
  };
  const auto select = [&](const usize i, const usize j, const usize k) {
    if (i < k)
      return false;
    if (i - j >= m)
      return true;
    return get(i, j) <= get(i, k);
  };
  const std::vector<usize> amax = smawk(n + m - 1, n, select);
  std::vector<T> c(n + m - 1);
  for (usize i = 0; i != n + m - 1; i += 1)
    c[i] = get(i, amax[i]);
  return c;
}

/**
 * @brief Concave Max Plus Convolution
 * @docs docs/concave_max_plus_convolution.md
 */
#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 2 "algorithm/smawk.cpp"

#include <functional>
#include <numeric>
#include <vector>

template <class Select>
std::vector<usize> smawk(const usize row_size, const usize col_size,
                         const Select &select) {
  using vec_zu = std::vector<usize>;

  const std::function<vec_zu(const vec_zu &, const vec_zu &)> solve =
      [&](const vec_zu &row, const vec_zu &col) -> vec_zu {
    const usize n = row.size();
    if (n == 0)
      return {};
    vec_zu c2;
    for (const usize i : col) {
      while (!c2.empty() && select(row[c2.size() - 1], c2.back(), i))
        c2.pop_back();
      if (c2.size() < n)
        c2.push_back(i);
    }
    vec_zu r2;
    for (usize i = 1; i < n; i += 2)
      r2.push_back(row[i]);
    const vec_zu a2 = solve(r2, c2);
    vec_zu ans(n);
    for (usize i = 0; i != a2.size(); i += 1)
      ans[i * 2 + 1] = a2[i];
    usize j = 0;
    for (usize i = 0; i < n; i += 2) {
      ans[i] = c2[j];
      const usize end = i + 1 == n ? c2.back() : ans[i + 1];
      while (c2[j] != end) {
        j += 1;
        if (select(row[i], ans[i], c2[j]))
          ans[i] = c2[j];
      }
    }
    return ans;
  };
  vec_zu row(row_size);
  std::iota(row.begin(), row.end(), 0);
  vec_zu col(col_size);
  std::iota(col.begin(), col.end(), 0);
  return solve(row, col);
}

/**
 * @brief SMAWK Algorithm
 * @docs docs/smawk.md
 */
#line 3 "algorithm/concave_max_plus_convolution.cpp"

#line 5 "algorithm/concave_max_plus_convolution.cpp"

template <class T>
std::vector<T> concave_max_plus_convolution(const std::vector<T> &a,
                                            const std::vector<T> &b) {
  const usize n = a.size();
  const usize m = b.size();
  const auto get = [&](const usize i, const usize j) {
    return a[j] + b[i - j];
  };
  const auto select = [&](const usize i, const usize j, const usize k) {
    if (i < k)
      return false;
    if (i - j >= m)
      return true;
    return get(i, j) <= get(i, k);
  };
  const std::vector<usize> amax = smawk(n + m - 1, n, select);
  std::vector<T> c(n + m - 1);
  for (usize i = 0; i != n + m - 1; i += 1)
    c[i] = get(i, amax[i]);
  return c;
}

/**
 * @brief Concave Max Plus Convolution
 * @docs docs/concave_max_plus_convolution.md
 */
Back to top page