convex/smawk.hpp

• View this file on GitHub
• Last update: 2023-10-24 13:33:26+09:00
• Include: #include "convex/smawk.hpp"
• Link: https://codeforces.com/contest/1423/problem/M

Required by

• convex/monge.hpp

Verified with

• test/mytest/smawk.test.cpp
• test/yukicoder/705.test.cpp

Code

#pragma once

// select(i,j,k) は (i,j) -> (i,k) を行うかどうか
// 残念ながら monotone minima より高速な場合が存在しない説がある
// https://codeforces.com/contest/1423/problem/M
template <typename F>
vc<int> smawk(int H, int W, F select) {
  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 (!select(x, py, y)) break;
        YY.pop_back();
      }
      if (len(YY) < len(X)) YY.eb(y);
    }
    vc<int> XX;
    FOR(i, 1, len(X), 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(i, 0, N, 2) {
      int LIM = (i + 1 == N ? Y.back() : I[i + 1]);
      int best = Y[p];
      while (Y[p] < LIM) {
        ++p;
        if (select(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 2 "convex/smawk.hpp"

// select(i,j,k) は (i,j) -> (i,k) を行うかどうか
// 残念ながら monotone minima より高速な場合が存在しない説がある
// https://codeforces.com/contest/1423/problem/M
template <typename F>
vc<int> smawk(int H, int W, F select) {
  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 (!select(x, py, y)) break;
        YY.pop_back();
      }
      if (len(YY) < len(X)) YY.eb(y);
    }
    vc<int> XX;
    FOR(i, 1, len(X), 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(i, 0, N, 2) {
      int LIM = (i + 1 == N ? Y.back() : I[i + 1]);
      int best = Y[p];
      while (Y[p] < LIM) {
        ++p;
        if (select(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);
}

Back to top page