monotone minima
(algorithm/monotone-minima.hpp)

• View this file on GitHub
• Last update: 2025-10-10 17:35:46+09:00
• Include: #include "algorithm/monotone-minima.hpp"

注意：以下では適当にタイブレークすることで $\operatorname{arg\,min}$ を集合ではなく添字を返す関数とみなす．

タイブレークは行によらないものならなんでもよい．

(totally) monotone

$N\times M$ 行列 $A=(A_{i,j})$ について，

\[i \leq i' \implies \operatorname{arg\,min}_{j}A_{i,j} \leq \operatorname{arg\,min}_{j}A_{i',j}\]

が成り立つとき $A$ は monotone であるという．

また $A$ の任意の部分行列が monotone であるとき，$A$ は totally monotone であるという．

monotone minima

$A$ は monotone とする． $i=1,2,\dots,N$ に対して $\operatorname{arg\,min}{j}A{i,j}$ を $O(M\log N)$ 時間で列挙できる．

まず $i_m\coloneqq\lfloor N/2\rfloor$ 行目の argmin $j_m$ を線形探索により $O(M)$ 時間で発見できる． その後，$[1,i,m-1]\times[1,j_m]$ と $[i_m+1,N]\times[j_m,M]$ の範囲それぞれについて再帰的に計算する．

$N\times M$ 行列を陽に持つとそれだけで $O(NM)$ 時間かかるので，実際には以下のようなものから計算することが多い．

• $(i,j)$ 成分と $(i,k)$ 成分を比較した結果を返す関数．
• $(i,j)$ 成分を返す関数．

応用: min-plus convolution

monotone minima を用いることで min-plus convolution が計算できる．

詳細は該当ライブラリのページを参照．

関連

(totally) monotone 性と関係している性質として Monge 性がある．

参照：[Monge まとめ①] Monge 性とは？

Required by

• min-plus 畳み込み (convex) (convolution/min-plus-convex.hpp)

Verified with

• verify/convolution/LC_min_plus_convolution_convex_arbitrary.test.cpp
• verify/convolution/LC_min_plus_convolution_convex_convex.test.cpp

Code

#pragma once

vector<int> MonotoneMinima(int n, int m, const function<bool(int, int, int)> &f) {
  vector<int> res(n);
  auto dfs = [&](auto rc, int il, int ir, int l, int r) -> void {
    if (il == ir) return;
    int i = (il + ir) / 2;
    int m = l;
    for (int k = l + 1; k < r; k++)
      if (!f(i, m, k)) m = k;
    res[i] = m;
    rc(rc, il, i, l, m + 1);
    rc(rc, i + 1, ir, m, r);
  };
  dfs(dfs, 0, n, 0, m);
  return res;
}

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

/**
 * @brief monotone minima
 * @docs docs/algorithm/monotone-minima.md
 */

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

vector<int> MonotoneMinima(int n, int m, const function<bool(int, int, int)> &f) {
  vector<int> res(n);
  auto dfs = [&](auto rc, int il, int ir, int l, int r) -> void {
    if (il == ir) return;
    int i = (il + ir) / 2;
    int m = l;
    for (int k = l + 1; k < r; k++)
      if (!f(i, m, k)) m = k;
    res[i] = m;
    rc(rc, il, i, l, m + 1);
    rc(rc, i + 1, ir, m, r);
  };
  dfs(dfs, 0, n, 0, m);
  return res;
}

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

/**
 * @brief monotone minima
 * @docs docs/algorithm/monotone-minima.md
 */

Back to top page