larsch.hpp¶
LARSCH algorithm for online row-minima of totally monotone matrices. Alternating row and column reductions recursively discard columns that can no longer be minimal. Total monotonicity makes row argmins nondecreasing, so each discarded candidate is charged once and rows can be exposed online.
在线产生全单调矩阵各行最小值；适合后一行转移依赖前面已算 DP 值的 Monge 优化。
Implementation¶
#ifndef NOYA_LARSCH_HPP
#define NOYA_LARSCH_HPP 1
/// @complexity Time: O(n + m) total for monotone row minima.
/// Space: O(n + m).
#include <functional>
#include <memory>
#include <vector>
namespace noya {
/// @brief LARSCH algorithm for online row-minima of totally monotone matrices.
/// Alternating row and column reductions recursively discard columns that can
/// no longer be minimal. Total monotonicity makes row argmins nondecreasing,
/// so each discarded candidate is charged once and rows can be exposed online.
template <class T> class larsch {
struct reduce_row;
struct reduce_col;
struct reduce_row {
int n;
std::function<T(int, int)> f;
int cur_row;
int state;
std::unique_ptr<reduce_col> rec;
reduce_row(int n_) : n(n_), f(), cur_row(0), state(0), rec() {
const int m = n / 2;
if (m != 0) {
rec = std::make_unique<reduce_col>(m);
}
}
void set_f(std::function<T(int, int)> f_) {
f = f_;
if (rec) {
rec->set_f([&](int i, int j) -> T { return f(2 * i + 1, j); });
}
}
int get_argmin() {
const int cur_row_ = cur_row;
cur_row += 1;
if (cur_row_ % 2 == 0) {
const int prev_argmin = state;
const int next_argmin = [&]() {
if (cur_row_ + 1 == n) {
return n - 1;
} else {
return rec->get_argmin();
}
}();
state = next_argmin;
int ret = prev_argmin;
for (int j = prev_argmin + 1; j <= next_argmin; j += 1) {
if (f(cur_row_, ret) > f(cur_row_, j)) {
ret = j;
}
}
return ret;
} else {
if (f(cur_row_, state) <= f(cur_row_, cur_row_)) {
return state;
} else {
return cur_row_;
}
}
}
};
struct reduce_col {
int n;
std::function<T(int, int)> f;
int cur_row;
std::vector<int> cols;
reduce_row rec;
reduce_col(int n_) : n(n_), f(), cur_row(0), cols(), rec(n) {}
void set_f(std::function<T(int, int)> f_) {
f = f_;
rec.set_f([&](int i, int j) -> T { return f(i, cols[j]); });
}
int get_argmin() {
const int cur_row_ = cur_row;
cur_row += 1;
const auto cs = [&]() -> std::vector<int> {
if (cur_row_ == 0) {
return {0};
} else {
return {{2 * cur_row_ - 1, 2 * cur_row_}};
}
}();
for (const int j : cs) {
while ([&]() {
const int size = cols.size();
return size != cur_row_ && f(size - 1, cols.back()) > f(size - 1, j);
}()) {
cols.pop_back();
}
if (cols.size() != n) {
cols.push_back(j);
}
}
return cols[rec.get_argmin()];
}
};
std::unique_ptr<reduce_row> base;
public:
larsch(int n, std::function<T(int, int)> f)
: base(std::make_unique<reduce_row>(n)) {
base->set_f(f);
}
/// @brief Return the column index of the minimum in the next row.
int get_argmin() { return base->get_argmin(); }
};
} // namespace noya
#endif // NOYA_LARSCH_HPP
#include <functional>
#include <memory>
#include <vector>
/// @complexity Time: O(n + m) total for monotone row minima.
/// Space: O(n + m).
namespace noya {
/// @brief LARSCH algorithm for online row-minima of totally monotone matrices.
/// Alternating row and column reductions recursively discard columns that can
/// no longer be minimal. Total monotonicity makes row argmins nondecreasing,
/// so each discarded candidate is charged once and rows can be exposed online.
template <class T> class larsch {
struct reduce_row;
struct reduce_col;
struct reduce_row {
int n;
std::function<T(int, int)> f;
int cur_row;
int state;
std::unique_ptr<reduce_col> rec;
reduce_row(int n_) : n(n_), f(), cur_row(0), state(0), rec() {
const int m = n / 2;
if (m != 0) {
rec = std::make_unique<reduce_col>(m);
}
}
void set_f(std::function<T(int, int)> f_) {
f = f_;
if (rec) {
rec->set_f([&](int i, int j) -> T { return f(2 * i + 1, j); });
}
}
int get_argmin() {
const int cur_row_ = cur_row;
cur_row += 1;
if (cur_row_ % 2 == 0) {
const int prev_argmin = state;
const int next_argmin = [&]() {
if (cur_row_ + 1 == n) {
return n - 1;
} else {
return rec->get_argmin();
}
}();
state = next_argmin;
int ret = prev_argmin;
for (int j = prev_argmin + 1; j <= next_argmin; j += 1) {
if (f(cur_row_, ret) > f(cur_row_, j)) {
ret = j;
}
}
return ret;
} else {
if (f(cur_row_, state) <= f(cur_row_, cur_row_)) {
return state;
} else {
return cur_row_;
}
}
}
};
struct reduce_col {
int n;
std::function<T(int, int)> f;
int cur_row;
std::vector<int> cols;
reduce_row rec;
reduce_col(int n_) : n(n_), f(), cur_row(0), cols(), rec(n) {}
void set_f(std::function<T(int, int)> f_) {
f = f_;
rec.set_f([&](int i, int j) -> T { return f(i, cols[j]); });
}
int get_argmin() {
const int cur_row_ = cur_row;
cur_row += 1;
const auto cs = [&]() -> std::vector<int> {
if (cur_row_ == 0) {
return {0};
} else {
return {{2 * cur_row_ - 1, 2 * cur_row_}};
}
}();
for (const int j : cs) {
while ([&]() {
const int size = cols.size();
return size != cur_row_ && f(size - 1, cols.back()) > f(size - 1, j);
}()) {
cols.pop_back();
}
if (cols.size() != n) {
cols.push_back(j);
}
}
return cols[rec.get_argmin()];
}
};
std::unique_ptr<reduce_row> base;
public:
larsch(int n, std::function<T(int, int)> f)
: base(std::make_unique<reduce_row>(n)) {
base->set_f(f);
}
/// @brief Return the column index of the minimum in the next row.
int get_argmin() { return base->get_argmin(); }
};
} // namespace noya