convex/smawk.hpp

View this file on GitHub
Last update: 2026-09-15 07:44:56+09:00
Include: #include "convex/smawk.hpp"

Required by

convex/monge/monge_dp_update.hpp

Verified with

Code

// 各行の最適列を求める.
// better(i,j,k): 行 i において列 k が列 j より良いとき true.
// 適用条件：totally monotone matrix.
template <typename F>
vc<int> smawk(int H, int W, F better) {
  if (H == 0) return {};
  assert(W > 0);

  auto dfs = [&](auto& dfs, vc<int> X, vc<int> Y) -> vc<int> {
    int N = len(X);
    if (N == 0) return {};

    vc<int> YY;
    for (auto&& y : Y) {
      while (len(YY)) {
        int py = YY.back(), x = X[len(YY) - 1];
        if (!better(x, py, y)) break;
        YY.pop_back();
      }
      if (len(YY) < len(X)) YY.eb(y);
    }

    vc<int> XX;
    for (int i = 1; i < len(X); i += 2) XX.eb(X[i]);

    vc<int> II = dfs(dfs, XX, YY);
    vc<int> I(N);
    FOR(i, len(II)) I[i + i + 1] = II[i];

    int p = 0;
    for (int i = 0; i < N; i += 2) {
      int lim = (i + 1 == N ? Y.back() : I[i + 1]);
      int best = Y[p];
      while (Y[p] < lim) {
        ++p;
        if (better(X[i], best, Y[p])) best = Y[p];
      }
      I[i] = best;
    }
    return I;
  };

  vc<int> X(H), Y(W);
  iota(all(X), 0), iota(all(Y), 0);
  return dfs(dfs, X, Y);
}

#line 1 "convex/smawk.hpp"

// 各行の最適列を求める.
// better(i,j,k): 行 i において列 k が列 j より良いとき true.
// 適用条件：totally monotone matrix.
template <typename F>
vc<int> smawk(int H, int W, F better) {
  if (H == 0) return {};
  assert(W > 0);

  auto dfs = [&](auto& dfs, vc<int> X, vc<int> Y) -> vc<int> {
    int N = len(X);
    if (N == 0) return {};

    vc<int> YY;
    for (auto&& y : Y) {
      while (len(YY)) {
        int py = YY.back(), x = X[len(YY) - 1];
        if (!better(x, py, y)) break;
        YY.pop_back();
      }
      if (len(YY) < len(X)) YY.eb(y);
    }

    vc<int> XX;
    for (int i = 1; i < len(X); i += 2) XX.eb(X[i]);

    vc<int> II = dfs(dfs, XX, YY);
    vc<int> I(N);
    FOR(i, len(II)) I[i + i + 1] = II[i];

    int p = 0;
    for (int i = 0; i < N; i += 2) {
      int lim = (i + 1 == N ? Y.back() : I[i + 1]);
      int best = Y[p];
      while (Y[p] < lim) {
        ++p;
        if (better(X[i], best, Y[p])) best = Y[p];
      }
      I[i] = best;
    }
    return I;
  };

  vc<int> X(H), Y(W);
  iota(all(X), 0), iota(all(Y), 0);
  return dfs(dfs, X, Y);
}