C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title 動的計画法/Li Chao tree(最小値) * * verification-helper: PROBLEM https://judge.yosupo.jp/problem/segment_add_get_min */ #include <iostream> #include <vector> #include "emthrm/dynamic_programming/li_chao_tree.hpp" int main() { constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; int n, q; std::cin >> n >> q; std::vector<int> query(q), l(n + q), r(n + q), a(n + q), p(q); std::vector<long long> b(n + q), xs; for (int i = 0; i < n; ++i) { std::cin >> l[i] >> r[i] >> a[i] >> b[i]; } for (int i = 0; i < q; ++i) { std::cin >> query[i]; if (query[i] == 0) { std::cin >> l[n + i] >> r[n + i] >> a[n + i] >> b[n + i]; } else if (query[i] == 1) { std::cin >> p[i]; xs.emplace_back(p[i]); } } if (xs.empty()) return 0; emthrm::LiChaoTree<long long> li_chao_tree(xs, LINF); for (int i = 0; i < n; ++i) { li_chao_tree.add(a[i], b[i], l[i], r[i]); } for (int i = 0; i < q; ++i) { if (query[i] == 0) { li_chao_tree.add(a[n + i], b[n + i], l[n + i], r[n + i]); } else if (query[i] == 1) { const long long ans = li_chao_tree.query(p[i]); if (ans == LINF) { std::cout << "INFINITY\n"; } else { std::cout << ans << '\n'; } } } return 0; }
#line 1 "test/dynamic_programming/li_chao_tree.1.test.cpp" /* * @title 動的計画法/Li Chao tree(最小値) * * verification-helper: PROBLEM https://judge.yosupo.jp/problem/segment_add_get_min */ #include <iostream> #include <vector> #line 1 "include/emthrm/dynamic_programming/li_chao_tree.hpp" #include <algorithm> #include <bit> #include <cassert> #include <iterator> #include <numeric> #include <utility> #line 11 "include/emthrm/dynamic_programming/li_chao_tree.hpp" namespace emthrm { template <typename T, bool IS_MINIMIZED = true> struct LiChaoTree { struct Line { T a, b; explicit Line(const T a, const T b) : a(a), b(b) {} T f(const T x) const { return a * x + b; } }; explicit LiChaoTree(const std::vector<T>& xs_, const T inf) : n(1), xs(xs_) { std::sort(xs.begin(), xs.end()); xs.erase(std::unique(xs.begin(), xs.end()), xs.end()); assert(xs.size() > 0); n = std::bit_ceil(xs.size()); const T xs_back = xs.back(); xs.resize(n, xs_back); dat.assign(n << 1, Line(0, inf)); } void add(T a, T b) { if constexpr (!IS_MINIMIZED) { a = -a; b = -b; } Line line(a, b); add(&line, 1, 0, n); } void add(T a, T b, T left, T right) { if constexpr (!IS_MINIMIZED) { a = -a; b = -b; } for (int len = 1, node_l = std::distance( xs.begin(), std::lower_bound(xs.begin(), xs.end(), left)), node_r = std::distance( xs.begin(), std::lower_bound(xs.begin(), xs.end(), right)), l = node_l + n, r = node_r + n; l < r; l >>= 1, r >>= 1, len <<= 1) { if (l & 1) { Line line(a, b); add(&line, l++, node_l, node_l + len); node_l += len; } if (r & 1) { Line line(a, b); node_r -= len; add(&line, --r, node_r, node_r + len); } } } T query(const T x) const { int node = n + std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), x)); T res = dat[node].f(x); while (node >>= 1) { if (dat[node].f(x) < res) res = dat[node].f(x); } return IS_MINIMIZED ? res : -res; } private: int n; std::vector<T> xs; std::vector<Line> dat; void add(Line* line, int node, int left, int right) { const bool flag_l = dat[node].f(xs[left]) <= line->f(xs[left]); const bool flag_r = dat[node].f(xs[right - 1]) <= line->f(xs[right - 1]); if (flag_l && flag_r) return; if (!flag_l && !flag_r) { std::swap(dat[node], *line); return; } const int mid = std::midpoint(left, right); if (line->f(xs[mid]) < dat[node].f(xs[mid])) std::swap(dat[node], *line); if (line->f(xs[left]) <= dat[node].f(xs[left])) { add(line, node << 1, left, mid); } else { add(line, (node << 1) + 1, mid, right); } } }; } // namespace emthrm #line 11 "test/dynamic_programming/li_chao_tree.1.test.cpp" int main() { constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; int n, q; std::cin >> n >> q; std::vector<int> query(q), l(n + q), r(n + q), a(n + q), p(q); std::vector<long long> b(n + q), xs; for (int i = 0; i < n; ++i) { std::cin >> l[i] >> r[i] >> a[i] >> b[i]; } for (int i = 0; i < q; ++i) { std::cin >> query[i]; if (query[i] == 0) { std::cin >> l[n + i] >> r[n + i] >> a[n + i] >> b[n + i]; } else if (query[i] == 1) { std::cin >> p[i]; xs.emplace_back(p[i]); } } if (xs.empty()) return 0; emthrm::LiChaoTree<long long> li_chao_tree(xs, LINF); for (int i = 0; i < n; ++i) { li_chao_tree.add(a[i], b[i], l[i], r[i]); } for (int i = 0; i < q; ++i) { if (query[i] == 0) { li_chao_tree.add(a[n + i], b[n + i], l[n + i], r[n + i]); } else if (query[i] == 1) { const long long ans = li_chao_tree.query(p[i]); if (ans == LINF) { std::cout << "INFINITY\n"; } else { std::cout << ans << '\n'; } } } return 0; }