description: 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.¶
smawk.hpp¶
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.
在线性查询次数内求全单调矩阵每一行的最小值位置；用于满足 Monge 性的离线 DP 优化。
Implementation¶
#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 row_size, const int col_size,
const Select &select) {
const std::function<std::vector<int>(const std::vector<int> &,
const std::vector<int> &)>
solve = [&](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() && select(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 = solve(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 (select(row[i], ans[i], c2[j]))
ans[i] = c2[j];
}
}
return ans;
};
std::vector<int> row(row_size);
std::iota(row.begin(), row.end(), 0);
std::vector<int> col(col_size);
std::iota(col.begin(), col.end(), 0);
return solve(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 row_size, const int col_size,
const Select &select) {
const std::function<std::vector<int>(const std::vector<int> &,
const std::vector<int> &)>
solve = [&](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() && select(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 = solve(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 (select(row[i], ans[i], c2[j]))
ans[i] = c2[j];
}
}
return ans;
};
std::vector<int> row(row_size);
std::iota(row.begin(), row.end(), 0);
std::vector<int> col(col_size);
std::iota(col.begin(), col.end(), 0);
return solve(row, col);
}
} // namespace noya