sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "data-structure/cht/undoable_li_chao_tree.hpp"
#pragma once #include <algorithm> #include <bit> #include <cassert> #include <limits> #include <utility> #include <vector> /** * @brief Undoable Li Chao Tree */ template <typename T> class UndoableLiChaoTree { public: UndoableLiChaoTree() = default; explicit UndoableLiChaoTree(const std::vector<T>& vs) : xs(vs) { std::ranges::sort(xs); xs.erase(std::ranges::unique(xs).begin(), xs.end()); size = std::bit_ceil(xs.size()); node.resize(2 * size, {0, INF}); while ((int)xs.size() <= size) xs.push_back(xs.back() + 1); } void add(T a, T b) { history.emplace_back(-1, Line(0, 0)); Line line(a, b); int k = 1, l = 0, r = size; while (true) { int m = std::midpoint(l, r); bool left = line(xs[l]) < node[k](xs[l]); bool mid = line(xs[m]) < node[k](xs[m]); bool right = line(xs[r]) < node[k](xs[r]); if (!left && !right) break; if (left && right) { history.emplace_back(k, node[k]); node[k] = line; break; } if (mid) { history.emplace_back(k, node[k]); std::swap(node[k], line); } if (r - l == 1) break; if (left != mid) { k = 2 * k; r = m; } else { k = 2 * k + 1; l = m; } } } T get(T x) const { int k = std::ranges::lower_bound(xs, x) - xs.begin(); k += size; T res = node[k](x); while (k >>= 1) res = std::min(res, node[k](x)); return res; } void undo() { assert(!history.empty()); while (true) { auto [k, line] = history.back(); history.pop_back(); if (k == -1) break; node[k] = line; } } private: struct Line { T a, b; Line(T a, T b) : a(a), b(b) {} T operator()(T x) const { return a * x + b; } }; static constexpr T INF = std::numeric_limits<T>::max(); int size; std::vector<T> xs; std::vector<Line> node; std::vector<std::pair<int, Line>> history; };
#line 2 "data-structure/cht/undoable_li_chao_tree.hpp" #include <algorithm> #include <bit> #include <cassert> #include <limits> #include <utility> #include <vector> /** * @brief Undoable Li Chao Tree */ template <typename T> class UndoableLiChaoTree { public: UndoableLiChaoTree() = default; explicit UndoableLiChaoTree(const std::vector<T>& vs) : xs(vs) { std::ranges::sort(xs); xs.erase(std::ranges::unique(xs).begin(), xs.end()); size = std::bit_ceil(xs.size()); node.resize(2 * size, {0, INF}); while ((int)xs.size() <= size) xs.push_back(xs.back() + 1); } void add(T a, T b) { history.emplace_back(-1, Line(0, 0)); Line line(a, b); int k = 1, l = 0, r = size; while (true) { int m = std::midpoint(l, r); bool left = line(xs[l]) < node[k](xs[l]); bool mid = line(xs[m]) < node[k](xs[m]); bool right = line(xs[r]) < node[k](xs[r]); if (!left && !right) break; if (left && right) { history.emplace_back(k, node[k]); node[k] = line; break; } if (mid) { history.emplace_back(k, node[k]); std::swap(node[k], line); } if (r - l == 1) break; if (left != mid) { k = 2 * k; r = m; } else { k = 2 * k + 1; l = m; } } } T get(T x) const { int k = std::ranges::lower_bound(xs, x) - xs.begin(); k += size; T res = node[k](x); while (k >>= 1) res = std::min(res, node[k](x)); return res; } void undo() { assert(!history.empty()); while (true) { auto [k, line] = history.back(); history.pop_back(); if (k == -1) break; node[k] = line; } } private: struct Line { T a, b; Line(T a, T b) : a(a), b(b) {} T operator()(T x) const { return a * x + b; } }; static constexpr T INF = std::numeric_limits<T>::max(); int size; std::vector<T> xs; std::vector<Line> node; std::vector<std::pair<int, Line>> history; };