sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "data-structure/cht/offline_deletable_convex_hull_trick.hpp"
直線の多重集合に対する以下のクエリをオフラインで処理する:
Undo 可能 Li Chao tree を用いて,offline dynamic connectivity の要領でこれを実現する.
空間計算量: $O(q\log q)$
void add(T a, T b)
void erase(T a, T b)
void get(T x)
vector<T> run()
get
#pragma once #include <bit> #include <cassert> #include <map> #include <utility> #include <vector> #include "undoable_li_chao_tree.hpp" template <typename T> class OfflineDeletableConvexHullTrick { public: void insert(T a, T b) { open.insert({{a, b}, now++}); } void erase(T a, T b) { auto it = open.find({a, b}); assert(it != open.end()); closed.emplace_back(a, b, it->second, now++); open.erase(it); } void get(T x) { query[now++] = x; xs.push_back(x); } std::vector<T> run() { if (xs.empty()) return {}; // erase lines for (auto [line, s] : open) { closed.emplace_back(line.first, line.second, s, now); } // build a segment tree int size = std::bit_ceil((unsigned int)now); std::vector<std::vector<std::pair<T, T>>> lines(2 * size); for (auto [a, b, s, t] : closed) { for (s += size, t += size; s < t; s >>= 1, t >>= 1) { if (s & 1) lines[s++].emplace_back(a, b); if (t & 1) lines[--t].emplace_back(a, b); } } // handle queries UndoableLiChaoTree<T> lct(xs); std::vector<T> ret; auto dfs = [&](const auto& dfs, int k) -> void { for (auto [a, b] : lines[k]) { lct.add(a, b); } if (k < size) { dfs(dfs, 2 * k); dfs(dfs, 2 * k + 1); } else if (k < size + now) { if (query.contains(k - size)) { ret.push_back(lct.get(query[k - size])); } } for (int i = 0; i < (int)lines[k].size(); ++i) { lct.undo(); } }; dfs(dfs, 1); return ret; } private: int now = 0; std::multimap<std::pair<T, T>, int> open; std::vector<std::tuple<T, T, int, int>> closed; std::map<int, T> query; std::vector<T> xs; };
#line 2 "data-structure/cht/offline_deletable_convex_hull_trick.hpp" #include <bit> #include <cassert> #include <map> #include <utility> #include <vector> #line 2 "data-structure/cht/undoable_li_chao_tree.hpp" #include <algorithm> #line 5 "data-structure/cht/undoable_li_chao_tree.hpp" #include <limits> #line 8 "data-structure/cht/undoable_li_chao_tree.hpp" /** * @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 9 "data-structure/cht/offline_deletable_convex_hull_trick.hpp" template <typename T> class OfflineDeletableConvexHullTrick { public: void insert(T a, T b) { open.insert({{a, b}, now++}); } void erase(T a, T b) { auto it = open.find({a, b}); assert(it != open.end()); closed.emplace_back(a, b, it->second, now++); open.erase(it); } void get(T x) { query[now++] = x; xs.push_back(x); } std::vector<T> run() { if (xs.empty()) return {}; // erase lines for (auto [line, s] : open) { closed.emplace_back(line.first, line.second, s, now); } // build a segment tree int size = std::bit_ceil((unsigned int)now); std::vector<std::vector<std::pair<T, T>>> lines(2 * size); for (auto [a, b, s, t] : closed) { for (s += size, t += size; s < t; s >>= 1, t >>= 1) { if (s & 1) lines[s++].emplace_back(a, b); if (t & 1) lines[--t].emplace_back(a, b); } } // handle queries UndoableLiChaoTree<T> lct(xs); std::vector<T> ret; auto dfs = [&](const auto& dfs, int k) -> void { for (auto [a, b] : lines[k]) { lct.add(a, b); } if (k < size) { dfs(dfs, 2 * k); dfs(dfs, 2 * k + 1); } else if (k < size + now) { if (query.contains(k - size)) { ret.push_back(lct.get(query[k - size])); } } for (int i = 0; i < (int)lines[k].size(); ++i) { lct.undo(); } }; dfs(dfs, 1); return ret; } private: int now = 0; std::multimap<std::pair<T, T>, int> open; std::vector<std::tuple<T, T, int, int>> closed; std::map<int, T> query; std::vector<T> xs; };