li_chao_tree.hpp¶
动态加入直线或线段，并在坐标点查询最小/最大函数值；适合斜率和查询顺序都不单调。
Complexity: Time: O(log n) per line/segment insertion or point query on n coordinates. Space: O(n).
AC 记录：line_add_get_min, segment_add_get_min。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log n) per line/segment insertion or point query on n coordinates.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <optional>
#include <vector>
namespace noya {
/// @brief Affine function k*x + b used by li_chao_tree.
template <class T> struct li_chao_line {
T k{};
T b{};
T operator()(const T &x) const { return k * x + b; }
};
/// @brief Li Chao tree on a fixed set of coordinates.
template <class T, bool Min = true> struct li_chao_tree {
using line_type = li_chao_line<T>;
std::vector<T> xs;
std::vector<std::optional<line_type>> seg;
li_chao_tree() = default;
explicit li_chao_tree(std::vector<T> poi) { build(std::move(poi)); }
/// @brief Rebuild on a sorted unique copy of the query coordinates.
void build(std::vector<T> poi) {
std::sort(poi.begin(), poi.end());
poi.erase(std::unique(poi.begin(), poi.end()), poi.end());
xs = std::move(poi);
seg.assign(std::max(1, int(xs.size()) * 4), std::nullopt);
}
/// @brief Add a line on every registered coordinate.
void add_line(line_type ln) {
if (!xs.empty()) {
add_line_at(1, 0, int(xs.size()), ln);
}
}
/// @brief Add a line on registered coordinates x in [l, r).
void add_segment(const T &l, const T &r, line_type ln) {
int bg = int(std::lower_bound(xs.begin(), xs.end(), l) - xs.begin());
int end = int(std::lower_bound(xs.begin(), xs.end(), r) - xs.begin());
if (bg < end) {
add_segment_at(1, 0, int(xs.size()), bg, end, ln);
}
}
/// @brief Query the optimum at a registered coordinate x.
T query(const T &x) const {
auto ans = query_optional(x);
assert(ans.has_value());
return *ans;
}
/// @brief Query the optimum at x, or nullopt when no active line covers x.
std::optional<T> query_optional(const T &x) const {
auto it = std::lower_bound(xs.begin(), xs.end(), x);
assert(it != xs.end() && *it == x);
return query_index_optional(int(it - xs.begin()));
}
/// @brief Query the optimum at xs[idx].
T query_index(int idx) const {
auto ans = query_index_optional(idx);
assert(ans.has_value());
return *ans;
}
/// @brief Query by coordinate index, or nullopt when it is uncovered.
std::optional<T> query_index_optional(int idx) const {
assert(0 <= idx && idx < int(xs.size()));
std::optional<T> ans;
query_at(1, 0, int(xs.size()), idx, ans);
return ans;
}
private:
static bool better(const T &l, const T &r) {
if constexpr (Min) {
return l < r;
} else {
return r < l;
}
}
void add_line_at(int nod, int l, int r, line_type ln) {
if (!seg[nod]) {
seg[nod] = ln;
return;
}
int mid = (l + r) / 2;
bool wl = better(ln(xs[l]), (*seg[nod])(xs[l]));
bool wm = better(ln(xs[mid]), (*seg[nod])(xs[mid]));
if (wm) {
std::swap(ln, *seg[nod]);
}
if (r - l == 1) {
return;
}
if (wl != wm) {
add_line_at(nod * 2, l, mid, ln);
} else {
add_line_at(nod * 2 + 1, mid, r, ln);
}
}
void add_segment_at(int nod, int l, int r, int ql, int qr, line_type ln) {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
add_line_at(nod, l, r, ln);
return;
}
int mid = (l + r) / 2;
add_segment_at(nod * 2, l, mid, ql, qr, ln);
add_segment_at(nod * 2 + 1, mid, r, ql, qr, ln);
}
void query_at(int nod, int l, int r, int idx, std::optional<T> &ans) const {
if (seg[nod]) {
T val = (*seg[nod])(xs[idx]);
if (!ans || better(val, *ans)) {
ans = val;
}
}
if (r - l == 1) {
return;
}
int mid = (l + r) / 2;
if (idx < mid) {
query_at(nod * 2, l, mid, idx, ans);
} else {
query_at(nod * 2 + 1, mid, r, idx, ans);
}
}
};
} // namespace noya
#ifndef NOYA_LI_CHAO_TREE_HPP
#define NOYA_LI_CHAO_TREE_HPP 1
/// @complexity Time: O(log n) per line/segment insertion or point query on n coordinates.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <optional>
#include <vector>
namespace noya {
/// @brief Affine function k*x + b used by li_chao_tree.
template <class T> struct li_chao_line {
T k{};
T b{};
T operator()(const T &x) const { return k * x + b; }
};
/// @brief Li Chao tree on a fixed set of coordinates.
template <class T, bool Min = true> struct li_chao_tree {
using line_type = li_chao_line<T>;
std::vector<T> xs;
std::vector<std::optional<line_type>> seg;
li_chao_tree() = default;
explicit li_chao_tree(std::vector<T> poi) { build(std::move(poi)); }
/// @brief Rebuild on a sorted unique copy of the query coordinates.
void build(std::vector<T> poi) {
std::sort(poi.begin(), poi.end());
poi.erase(std::unique(poi.begin(), poi.end()), poi.end());
xs = std::move(poi);
seg.assign(std::max(1, int(xs.size()) * 4), std::nullopt);
}
/// @brief Add a line on every registered coordinate.
void add_line(line_type ln) {
if (!xs.empty()) {
add_line_at(1, 0, int(xs.size()), ln);
}
}
/// @brief Add a line on registered coordinates x in [l, r).
void add_segment(const T &l, const T &r, line_type ln) {
int bg = int(std::lower_bound(xs.begin(), xs.end(), l) - xs.begin());
int end = int(std::lower_bound(xs.begin(), xs.end(), r) - xs.begin());
if (bg < end) {
add_segment_at(1, 0, int(xs.size()), bg, end, ln);
}
}
/// @brief Query the optimum at a registered coordinate x.
T query(const T &x) const {
auto ans = query_optional(x);
assert(ans.has_value());
return *ans;
}
/// @brief Query the optimum at x, or nullopt when no active line covers x.
std::optional<T> query_optional(const T &x) const {
auto it = std::lower_bound(xs.begin(), xs.end(), x);
assert(it != xs.end() && *it == x);
return query_index_optional(int(it - xs.begin()));
}
/// @brief Query the optimum at xs[idx].
T query_index(int idx) const {
auto ans = query_index_optional(idx);
assert(ans.has_value());
return *ans;
}
/// @brief Query by coordinate index, or nullopt when it is uncovered.
std::optional<T> query_index_optional(int idx) const {
assert(0 <= idx && idx < int(xs.size()));
std::optional<T> ans;
query_at(1, 0, int(xs.size()), idx, ans);
return ans;
}
private:
static bool better(const T &l, const T &r) {
if constexpr (Min) {
return l < r;
} else {
return r < l;
}
}
void add_line_at(int nod, int l, int r, line_type ln) {
if (!seg[nod]) {
seg[nod] = ln;
return;
}
int mid = (l + r) / 2;
bool wl = better(ln(xs[l]), (*seg[nod])(xs[l]));
bool wm = better(ln(xs[mid]), (*seg[nod])(xs[mid]));
if (wm) {
std::swap(ln, *seg[nod]);
}
if (r - l == 1) {
return;
}
if (wl != wm) {
add_line_at(nod * 2, l, mid, ln);
} else {
add_line_at(nod * 2 + 1, mid, r, ln);
}
}
void add_segment_at(int nod, int l, int r, int ql, int qr, line_type ln) {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
add_line_at(nod, l, r, ln);
return;
}
int mid = (l + r) / 2;
add_segment_at(nod * 2, l, mid, ql, qr, ln);
add_segment_at(nod * 2 + 1, mid, r, ql, qr, ln);
}
void query_at(int nod, int l, int r, int idx, std::optional<T> &ans) const {
if (seg[nod]) {
T val = (*seg[nod])(xs[idx]);
if (!ans || better(val, *ans)) {
ans = val;
}
}
if (r - l == 1) {
return;
}
int mid = (l + r) / 2;
if (idx < mid) {
query_at(nod * 2, l, mid, idx, ans);
} else {
query_at(nod * 2 + 1, mid, r, idx, ans);
}
}
};
} // namespace noya
#endif // NOYA_LI_CHAO_TREE_HPP
#include <algorithm>
#include <cassert>
#include <optional>
#include <vector>
/// @complexity Time: O(log n) per line/segment insertion or point query on n coordinates.
/// Space: O(n).
namespace noya {
/// @brief Affine function k*x + b used by li_chao_tree.
template <class T> struct li_chao_line {
T k{};
T b{};
T operator()(const T &x) const { return k * x + b; }
};
/// @brief Li Chao tree on a fixed set of coordinates.
template <class T, bool Min = true> struct li_chao_tree {
using line_type = li_chao_line<T>;
std::vector<T> xs;
std::vector<std::optional<line_type>> seg;
li_chao_tree() = default;
explicit li_chao_tree(std::vector<T> poi) { build(std::move(poi)); }
/// @brief Rebuild on a sorted unique copy of the query coordinates.
void build(std::vector<T> poi) {
std::sort(poi.begin(), poi.end());
poi.erase(std::unique(poi.begin(), poi.end()), poi.end());
xs = std::move(poi);
seg.assign(std::max(1, int(xs.size()) * 4), std::nullopt);
}
/// @brief Add a line on every registered coordinate.
void add_line(line_type ln) {
if (!xs.empty()) {
add_line_at(1, 0, int(xs.size()), ln);
}
}
/// @brief Add a line on registered coordinates x in [l, r).
void add_segment(const T &l, const T &r, line_type ln) {
int bg = int(std::lower_bound(xs.begin(), xs.end(), l) - xs.begin());
int end = int(std::lower_bound(xs.begin(), xs.end(), r) - xs.begin());
if (bg < end) {
add_segment_at(1, 0, int(xs.size()), bg, end, ln);
}
}
/// @brief Query the optimum at a registered coordinate x.
T query(const T &x) const {
auto ans = query_optional(x);
assert(ans.has_value());
return *ans;
}
/// @brief Query the optimum at x, or nullopt when no active line covers x.
std::optional<T> query_optional(const T &x) const {
auto it = std::lower_bound(xs.begin(), xs.end(), x);
assert(it != xs.end() && *it == x);
return query_index_optional(int(it - xs.begin()));
}
/// @brief Query the optimum at xs[idx].
T query_index(int idx) const {
auto ans = query_index_optional(idx);
assert(ans.has_value());
return *ans;
}
/// @brief Query by coordinate index, or nullopt when it is uncovered.
std::optional<T> query_index_optional(int idx) const {
assert(0 <= idx && idx < int(xs.size()));
std::optional<T> ans;
query_at(1, 0, int(xs.size()), idx, ans);
return ans;
}
private:
static bool better(const T &l, const T &r) {
if constexpr (Min) {
return l < r;
} else {
return r < l;
}
}
void add_line_at(int nod, int l, int r, line_type ln) {
if (!seg[nod]) {
seg[nod] = ln;
return;
}
int mid = (l + r) / 2;
bool wl = better(ln(xs[l]), (*seg[nod])(xs[l]));
bool wm = better(ln(xs[mid]), (*seg[nod])(xs[mid]));
if (wm) {
std::swap(ln, *seg[nod]);
}
if (r - l == 1) {
return;
}
if (wl != wm) {
add_line_at(nod * 2, l, mid, ln);
} else {
add_line_at(nod * 2 + 1, mid, r, ln);
}
}
void add_segment_at(int nod, int l, int r, int ql, int qr, line_type ln) {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
add_line_at(nod, l, r, ln);
return;
}
int mid = (l + r) / 2;
add_segment_at(nod * 2, l, mid, ql, qr, ln);
add_segment_at(nod * 2 + 1, mid, r, ql, qr, ln);
}
void query_at(int nod, int l, int r, int idx, std::optional<T> &ans) const {
if (seg[nod]) {
T val = (*seg[nod])(xs[idx]);
if (!ans || better(val, *ans)) {
ans = val;
}
}
if (r - l == 1) {
return;
}
int mid = (l + r) / 2;
if (idx < mid) {
query_at(nod * 2, l, mid, idx, ans);
} else {
query_at(nod * 2 + 1, mid, r, idx, ans);
}
}
};
} // namespace noya