smawk.hpp¶

SECTIONOptimization INCLUDEnoya/smawk.hpp

在线性查询次数内求全单调矩阵每一行的最小值位置；用于满足 Monge 性的离线 DP 优化。

Complexity: Time: O(rows + columns) matrix probes. Space: O(rows + columns).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(rows + columns) matrix probes.
/// Space: O(rows + columns).

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

namespace noya {

/// @brief SMAWK algorithm: compute row minima of a totally monotone matrix.
/// A stack reduction leaves at most one candidate column per row, recursion
/// solves the odd rows, and monotone argmins bound the scan that interpolates
/// each even row. Every row and column is discarded or scanned only O(1) times.
/// @return Vector where ans[i] is the column index of the minimum in row i.
template <class Select>
std::vector<int> smawk(const int nr, const int nc, const Select &sel) {
  const std::function<std::vector<int>(const std::vector<int> &,
                                       const std::vector<int> &)>
      sol = [&](const std::vector<int> &row,
                const std::vector<int> &col) -> std::vector<int> {
    const int n = int(row.size());
    if (n == 0)
      return {};
    std::vector<int> c2;
    for (const int i : col) {
      while (!c2.empty() && sel(row[c2.size() - 1], c2.back(), i))
        c2.pop_back();
      if (c2.size() < n)
        c2.push_back(i);
    }
    std::vector<int> r2;
    for (int i = 1; i < n; i += 2)
      r2.push_back(row[i]);
    const std::vector<int> a2 = sol(r2, c2);
    std::vector<int> ans(n);
    for (int i = 0; i != a2.size(); i += 1)
      ans[i * 2 + 1] = a2[i];
    int j = 0;
    for (int i = 0; i < n; i += 2) {
      ans[i] = c2[j];
      const int end = i + 1 == n ? c2.back() : ans[i + 1];
      while (c2[j] != end) {
        j += 1;
        if (sel(row[i], ans[i], c2[j]))
          ans[i] = c2[j];
      }
    }
    return ans;
  };
  std::vector<int> row(nr);
  std::iota(row.begin(), row.end(), 0);
  std::vector<int> col(nc);
  std::iota(col.begin(), col.end(), 0);
  return sol(row, col);
}

} // namespace noya

#ifndef NOYA_SMAWK_HPP
#define NOYA_SMAWK_HPP 1

/// @complexity Time: O(rows + columns) matrix probes.
/// Space: O(rows + columns).

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

namespace noya {

/// @brief SMAWK algorithm: compute row minima of a totally monotone matrix.
/// A stack reduction leaves at most one candidate column per row, recursion
/// solves the odd rows, and monotone argmins bound the scan that interpolates
/// each even row. Every row and column is discarded or scanned only O(1) times.
/// @return Vector where ans[i] is the column index of the minimum in row i.
template <class Select>
std::vector<int> smawk(const int nr, const int nc, const Select &sel) {
  const std::function<std::vector<int>(const std::vector<int> &,
                                       const std::vector<int> &)>
      sol = [&](const std::vector<int> &row,
                const std::vector<int> &col) -> std::vector<int> {
    const int n = int(row.size());
    if (n == 0)
      return {};
    std::vector<int> c2;
    for (const int i : col) {
      while (!c2.empty() && sel(row[c2.size() - 1], c2.back(), i))
        c2.pop_back();
      if (c2.size() < n)
        c2.push_back(i);
    }
    std::vector<int> r2;
    for (int i = 1; i < n; i += 2)
      r2.push_back(row[i]);
    const std::vector<int> a2 = sol(r2, c2);
    std::vector<int> ans(n);
    for (int i = 0; i != a2.size(); i += 1)
      ans[i * 2 + 1] = a2[i];
    int j = 0;
    for (int i = 0; i < n; i += 2) {
      ans[i] = c2[j];
      const int end = i + 1 == n ? c2.back() : ans[i + 1];
      while (c2[j] != end) {
        j += 1;
        if (sel(row[i], ans[i], c2[j]))
          ans[i] = c2[j];
      }
    }
    return ans;
  };
  std::vector<int> row(nr);
  std::iota(row.begin(), row.end(), 0);
  std::vector<int> col(nc);
  std::iota(col.begin(), col.end(), 0);
  return sol(row, col);
}

} // namespace noya

#endif // NOYA_SMAWK_HPP

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

/// @complexity Time: O(rows + columns) matrix probes.
/// Space: O(rows + columns).

namespace noya {

/// @brief SMAWK algorithm: compute row minima of a totally monotone matrix.
/// A stack reduction leaves at most one candidate column per row, recursion
/// solves the odd rows, and monotone argmins bound the scan that interpolates
/// each even row. Every row and column is discarded or scanned only O(1) times.
/// @return Vector where ans[i] is the column index of the minimum in row i.
template <class Select>
std::vector<int> smawk(const int nr, const int nc, const Select &sel) {
  const std::function<std::vector<int>(const std::vector<int> &,
                                       const std::vector<int> &)>
      sol = [&](const std::vector<int> &row,
                const std::vector<int> &col) -> std::vector<int> {
    const int n = int(row.size());
    if (n == 0)
      return {};
    std::vector<int> c2;
    for (const int i : col) {
      while (!c2.empty() && sel(row[c2.size() - 1], c2.back(), i))
        c2.pop_back();
      if (c2.size() < n)
        c2.push_back(i);
    }
    std::vector<int> r2;
    for (int i = 1; i < n; i += 2)
      r2.push_back(row[i]);
    const std::vector<int> a2 = sol(r2, c2);
    std::vector<int> ans(n);
    for (int i = 0; i != a2.size(); i += 1)
      ans[i * 2 + 1] = a2[i];
    int j = 0;
    for (int i = 0; i < n; i += 2) {
      ans[i] = c2[j];
      const int end = i + 1 == n ? c2.back() : ans[i + 1];
      while (c2[j] != end) {
        j += 1;
        if (sel(row[i], ans[i], c2[j]))
          ans[i] = c2[j];
      }
    }
    return ans;
  };
  std::vector<int> row(nr);
  std::iota(row.begin(), row.end(), 0);
  std::vector<int> col(nc);
  std::iota(col.begin(), col.end(), 0);
  return sol(row, col);
}

} // namespace noya