larsch.hpp¶
在线产生全单调矩阵各行最小值；适合后一行转移依赖前面已算 DP 值的 Monge 优化。
Complexity: Time: O(n + m) total for monotone row minima. Space: O(n + m).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 cr;
int st;
std::unique_ptr<reduce_col> rec;
reduce_row(int n_) : n(n_), f(), cr(0), st(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 cr_ = cr;
cr += 1;
if (cr_ % 2 == 0) {
const int pa = st;
const int na = [&]() {
if (cr_ + 1 == n) {
return n - 1;
} else {
return rec->get_argmin();
}
}();
st = na;
int ret = pa;
for (int j = pa + 1; j <= na; j += 1) {
if (f(cr_, ret) > f(cr_, j)) {
ret = j;
}
}
return ret;
} else {
if (f(cr_, st) <= f(cr_, cr_)) {
return st;
} else {
return cr_;
}
}
}
};
struct reduce_col {
int n;
std::function<T(int, int)> f;
int cr;
std::vector<int> col;
reduce_row rec;
reduce_col(int n_) : n(n_), f(), cr(0), col(), rec(n) {}
void set_f(std::function<T(int, int)> f_) {
f = f_;
rec.set_f([&](int i, int j) -> T { return f(i, col[j]); });
}
int get_argmin() {
const int cr_ = cr;
cr += 1;
const auto cs = [&]() -> std::vector<int> {
if (cr_ == 0) {
return {0};
} else {
return {{2 * cr_ - 1, 2 * cr_}};
}
}();
for (const int j : cs) {
while ([&]() {
const int sz = col.size();
return sz != cr_ && f(sz - 1, col.back()) > f(sz - 1, j);
}()) {
col.pop_back();
}
if (col.size() != n) {
col.push_back(j);
}
}
return col[rec.get_argmin()];
}
};
std::unique_ptr<reduce_row> bas;
public:
larsch(int n, std::function<T(int, int)> f)
: bas(std::make_unique<reduce_row>(n)) {
bas->set_f(f);
}
/// @brief Return the column index of the minimum in the next row.
int get_argmin() { return bas->get_argmin(); }
};
} // namespace noya
#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 cr;
int st;
std::unique_ptr<reduce_col> rec;
reduce_row(int n_) : n(n_), f(), cr(0), st(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 cr_ = cr;
cr += 1;
if (cr_ % 2 == 0) {
const int pa = st;
const int na = [&]() {
if (cr_ + 1 == n) {
return n - 1;
} else {
return rec->get_argmin();
}
}();
st = na;
int ret = pa;
for (int j = pa + 1; j <= na; j += 1) {
if (f(cr_, ret) > f(cr_, j)) {
ret = j;
}
}
return ret;
} else {
if (f(cr_, st) <= f(cr_, cr_)) {
return st;
} else {
return cr_;
}
}
}
};
struct reduce_col {
int n;
std::function<T(int, int)> f;
int cr;
std::vector<int> col;
reduce_row rec;
reduce_col(int n_) : n(n_), f(), cr(0), col(), rec(n) {}
void set_f(std::function<T(int, int)> f_) {
f = f_;
rec.set_f([&](int i, int j) -> T { return f(i, col[j]); });
}
int get_argmin() {
const int cr_ = cr;
cr += 1;
const auto cs = [&]() -> std::vector<int> {
if (cr_ == 0) {
return {0};
} else {
return {{2 * cr_ - 1, 2 * cr_}};
}
}();
for (const int j : cs) {
while ([&]() {
const int sz = col.size();
return sz != cr_ && f(sz - 1, col.back()) > f(sz - 1, j);
}()) {
col.pop_back();
}
if (col.size() != n) {
col.push_back(j);
}
}
return col[rec.get_argmin()];
}
};
std::unique_ptr<reduce_row> bas;
public:
larsch(int n, std::function<T(int, int)> f)
: bas(std::make_unique<reduce_row>(n)) {
bas->set_f(f);
}
/// @brief Return the column index of the minimum in the next row.
int get_argmin() { return bas->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 cr;
int st;
std::unique_ptr<reduce_col> rec;
reduce_row(int n_) : n(n_), f(), cr(0), st(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 cr_ = cr;
cr += 1;
if (cr_ % 2 == 0) {
const int pa = st;
const int na = [&]() {
if (cr_ + 1 == n) {
return n - 1;
} else {
return rec->get_argmin();
}
}();
st = na;
int ret = pa;
for (int j = pa + 1; j <= na; j += 1) {
if (f(cr_, ret) > f(cr_, j)) {
ret = j;
}
}
return ret;
} else {
if (f(cr_, st) <= f(cr_, cr_)) {
return st;
} else {
return cr_;
}
}
}
};
struct reduce_col {
int n;
std::function<T(int, int)> f;
int cr;
std::vector<int> col;
reduce_row rec;
reduce_col(int n_) : n(n_), f(), cr(0), col(), rec(n) {}
void set_f(std::function<T(int, int)> f_) {
f = f_;
rec.set_f([&](int i, int j) -> T { return f(i, col[j]); });
}
int get_argmin() {
const int cr_ = cr;
cr += 1;
const auto cs = [&]() -> std::vector<int> {
if (cr_ == 0) {
return {0};
} else {
return {{2 * cr_ - 1, 2 * cr_}};
}
}();
for (const int j : cs) {
while ([&]() {
const int sz = col.size();
return sz != cr_ && f(sz - 1, col.back()) > f(sz - 1, j);
}()) {
col.pop_back();
}
if (col.size() != n) {
col.push_back(j);
}
}
return col[rec.get_argmin()];
}
};
std::unique_ptr<reduce_row> bas;
public:
larsch(int n, std::function<T(int, int)> f)
: bas(std::make_unique<reduce_row>(n)) {
bas->set_f(f);
}
/// @brief Return the column index of the minimum in the next row.
int get_argmin() { return bas->get_argmin(); }
};
} // namespace noya