library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unit/li_chao_tree.test.cpp
- View this file on GitHub
- Last update: 2026-10-26 22:16:38+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <optional>
#include <random>
#include <vector>
#include "datastructure/li_chao_tree.hpp"
int main() {
std::mt19937 rng(5);
for (int it = 0; it < 3000; it++) {
long long lo = (long long)(rng() % 41) - 20;
long long hi = lo + 1 + rng() % 40;
li_chao_tree<long long> t(lo, hi);
std::vector<std::array<long long, 4>> segs;
int ops = rng() % 8;
for (int k = 0; k < ops; k++) {
long long a = (long long)(rng() % 21) - 10, b = (long long)(rng() % 201) - 100;
if (rng() % 2) {
t.add_line(a, b);
segs.push_back({a, b, lo, hi});
} else {
long long l = lo + rng() % (hi - lo + 1), r = lo + rng() % (hi - lo + 1);
if (l > r) std::swap(l, r);
t.add_segment(a, b, l, r);
segs.push_back({a, b, l, r});
}
}
for (long long x = lo; x < hi; x++) {
std::optional<long long> best;
for (auto [a, b, l, r] : segs)
if (l <= x && x < r && (!best || a * x + b < *best)) best = a * x + b;
assert(t.min(x) == best);
}
}
// the case the old implementation got wrong
{
li_chao_tree<long long> t(-20, 21);
for (auto [a, b] : {std::pair{5, -62}, {-8, 49}, {-1, -50}, {-4, 8}, {-7, 16}, {-1, -22}}) t.add_line(a, b);
assert(t.min(10) == -60);
}
// large coordinates, double values
{
li_chao_tree<double> t(-1000000000, 1000000001);
t.add_line(0.5, 1.0);
t.add_segment(-0.5, 2.0, 0, 10);
assert(*t.min(4) == 0.0);
assert(*t.min(100) == 51.0);
assert(!li_chao_tree<long long>(0, 10).min(3));
}
std::cout << "Hello World" << std::endl;
}#line 1 "test/unit/li_chao_tree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <optional>
#include <random>
#include <vector>
#line 5 "datastructure/li_chao_tree.hpp"
#include <utility>
#line 7 "datastructure/li_chao_tree.hpp"
template <class T> struct li_chao_tree {
li_chao_tree(long long lo, long long hi) : lo(lo), hi(hi) {
assert(lo < hi);
make_node();
}
void add_line(T a, T b) { add_line(0, lo, hi, a, b); }
void add_segment(T a, T b, long long l, long long r) {
assert(lo <= l && l <= r && r <= hi);
add_segment(0, lo, hi, l, r, a, b);
}
std::optional<T> min(long long x) const {
assert(lo <= x && x < hi);
std::optional<T> res;
long long l = lo, r = hi;
for (int t = 0; t != -1;) {
const node& v = get(t);
if (v.has) {
T y = v.a * x + v.b;
if (!res || y < *res) res = y;
}
long long m = l + (r - l) / 2;
if (x < m) {
r = m;
t = v.left;
} else {
l = m;
t = v.right;
}
}
return res;
}
private:
struct node {
T a = 0, b = 0;
bool has = false;
int left = -1, right = -1;
};
static constexpr int chunk_log = 16;
long long lo, hi;
int num_nodes = 0;
std::vector<std::vector<node>> chunks;
node& get(int t) { return chunks[t >> chunk_log][t & ((1 << chunk_log) - 1)]; }
const node& get(int t) const {
return chunks[t >> chunk_log][t & ((1 << chunk_log) - 1)];
}
int make_node() {
if ((num_nodes & ((1 << chunk_log) - 1)) == 0) {
chunks.emplace_back();
chunks.back().reserve(1 << chunk_log);
}
chunks.back().push_back({});
return num_nodes++;
}
void add_line(int t, long long l, long long r, T a, T b) {
while (true) {
node& v = get(t);
if (!v.has) {
v.a = a, v.b = b, v.has = true;
return;
}
bool left_better = a * l + b < v.a * l + v.b;
bool right_better = a * (r - 1) + b < v.a * (r - 1) + v.b;
if (left_better && right_better) {
v.a = a, v.b = b;
return;
}
if (!left_better && !right_better) return;
long long m = l + (r - l) / 2;
bool mid_better = a * m + b < v.a * m + v.b;
if (mid_better) std::swap(v.a, a), std::swap(v.b, b);
if (left_better != mid_better) {
if (get(t).left == -1) get(t).left = make_node();
t = get(t).left, r = m;
} else {
if (get(t).right == -1) get(t).right = make_node();
t = get(t).right, l = m;
}
}
}
void add_segment(int t, long long l, long long r, long long ql, long long qr,
T a, T b) {
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) {
add_line(t, l, r, a, b);
return;
}
long long m = l + (r - l) / 2;
if (ql < m) {
if (get(t).left == -1) get(t).left = make_node();
add_segment(get(t).left, l, m, ql, qr, a, b);
}
if (m < qr) {
if (get(t).right == -1) get(t).right = make_node();
add_segment(get(t).right, m, r, ql, qr, a, b);
}
}
};
#line 11 "test/unit/li_chao_tree.test.cpp"
int main() {
std::mt19937 rng(5);
for (int it = 0; it < 3000; it++) {
long long lo = (long long)(rng() % 41) - 20;
long long hi = lo + 1 + rng() % 40;
li_chao_tree<long long> t(lo, hi);
std::vector<std::array<long long, 4>> segs;
int ops = rng() % 8;
for (int k = 0; k < ops; k++) {
long long a = (long long)(rng() % 21) - 10, b = (long long)(rng() % 201) - 100;
if (rng() % 2) {
t.add_line(a, b);
segs.push_back({a, b, lo, hi});
} else {
long long l = lo + rng() % (hi - lo + 1), r = lo + rng() % (hi - lo + 1);
if (l > r) std::swap(l, r);
t.add_segment(a, b, l, r);
segs.push_back({a, b, l, r});
}
}
for (long long x = lo; x < hi; x++) {
std::optional<long long> best;
for (auto [a, b, l, r] : segs)
if (l <= x && x < r && (!best || a * x + b < *best)) best = a * x + b;
assert(t.min(x) == best);
}
}
// the case the old implementation got wrong
{
li_chao_tree<long long> t(-20, 21);
for (auto [a, b] : {std::pair{5, -62}, {-8, 49}, {-1, -50}, {-4, 8}, {-7, 16}, {-1, -22}}) t.add_line(a, b);
assert(t.min(10) == -60);
}
// large coordinates, double values
{
li_chao_tree<double> t(-1000000000, 1000000001);
t.add_line(0.5, 1.0);
t.add_segment(-0.5, 2.0, 0, 10);
assert(*t.min(4) == 0.0);
assert(*t.min(100) == 51.0);
assert(!li_chao_tree<long long>(0, 10).min(3));
}
std::cout << "Hello World" << std::endl;
}