larsch.hpp¶
在线求全单调下三角矩阵的行最小值；每行只考虑对角线及其左侧，适合转移依赖已算 DP 值的 Monge 优化。
Complexity: Time: \(O(n)\) total bookkeeping and matrix probes for \(n\) row minima. Space: \(O(n)\), excluding callback state.
Source: noshi91
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n) total bookkeeping and matrix probes for n row minima.
/// Space: O(n), excluding callback state.
#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.
/// Row i considers columns [0, i]. During call i, probes may inspect later
/// rows, but never columns beyond i.
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;
// The first row introduces one column; later rows introduce two.
for (int j = cr_ == 0 ? 0 : 2 * cr_ - 1; j <= 2 * cr_; j++) {
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 next row's minimum column; call at most n times.
int get_argmin() { return bas->get_argmin(); }
};
} // namespace noya
// NOYA_LARSCH_HPP
#ifndef NOYA_LARSCH_HPP
#define NOYA_LARSCH_HPP 1
/// @complexity Time: O(n) total bookkeeping and matrix probes for n row minima.
/// Space: O(n), excluding callback state.
#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.
/// Row i considers columns [0, i]. During call i, probes may inspect later
/// rows, but never columns beyond i.
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;
// The first row introduces one column; later rows introduce two.
for (int j = cr_ == 0 ? 0 : 2 * cr_ - 1; j <= 2 * cr_; j++) {
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 next row's minimum column; call at most n times.
int get_argmin() { return bas->get_argmin(); }
};
} // namespace noya
#endif // NOYA_LARSCH_HPP
/// @complexity Time: O(n) total bookkeeping and matrix probes for n row minima.
/// Space: O(n), excluding callback state.
#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.
/// Row i considers columns [0, i]. During call i, probes may inspect later
/// rows, but never columns beyond i.
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;
// The first row introduces one column; later rows introduce two.
for (int j = cr_ == 0 ? 0 : 2 * cr_ - 1; j <= 2 * cr_; j++) {
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 next row's minimum column; call at most n times.
int get_argmin() { return bas->get_argmin(); }
};
} // namespace noya
// NOYA_LARSCH_HPP