This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// @brief Convex Hull Trick (Li-Chao Tree) template <typename X_Tp, typename Y_Tp> struct LiChaoTree { private: vector<X_Tp> X_pos; Y_Tp E; function<bool(Y_Tp, Y_Tp)> comp; int N; // @brief Line: 直線のクラス struct Line { bool is_empty; Y_Tp a, b; int index; Line() { is_empty = true; } Line(Y_Tp a_, Y_Tp b_, int index_) : a(a_), b(b_), index(index_) { is_empty = false; } bool empty() const { return is_empty; } Y_Tp f(X_Tp x) const { return a*x + b; } }; vector<Line> node; void node_update(Line line, int t1, int t2, int l, int r, int k) { int mid = (l + r) / 2; if(t2 <= l or r <= t1) return; if(t1 <= l and r <= t2) { if(node[k].empty()) { node[k] = line; return; } if(comp(line.f(X_pos[l]), node[k].f(X_pos[l])) and comp(line.f(X_pos[r-1]), node[k].f(X_pos[r-1]))) return; if(comp(node[k].f(X_pos[l]), line.f(X_pos[l])) and comp(node[k].f(X_pos[r-1]), line.f(X_pos[r-1]))) { node[k] = line; return; } if(r - l == 1) return; if(comp(node[k].f(X_pos[mid]), line.f(X_pos[mid]))) { swap(line, node[k]); } if(comp(node[k].f(X_pos[l]), line.f(X_pos[l]))) { node_update(line, t1, t2, l, mid, 2*k+1); } else { node_update(line, t1, t2, mid, r, 2*k+2); } } else { node_update(line, t1, t2, l, mid, 2*k+1); node_update(line, t1, t2, mid, r, 2*k+2); } } pair<Y_Tp, int> search_line(int t) const { pair<Y_Tp, int> result(E, -1); int l = 0, r = N, k = 0; while(true) { if(!node[k].empty()) { pair<Y_Tp, int> cand(node[k].f(X_pos[t]), node[k].index); if(comp(result.first, cand.first)) result = cand; } if(r - l == 1) break; int mid = (l + r) / 2; if(t < mid) r = mid, k = 2*k + 1; else l = mid, k = 2*k + 2; } return result; } public: // @brief クエリが与えられる座標・単位元・比較関数を渡す LiChaoTree(vector<X_Tp> X_pos_, Y_Tp E_, function<bool(Y_Tp, Y_Tp)> comp_) : X_pos(X_pos_), E(E_), comp(comp_) { sort(X_pos.begin(), X_pos.end()); X_pos.erase(unique(X_pos.begin(), X_pos.end()), X_pos.end()); N = 1; while(N < X_pos.size()) N <<= 1; while(X_pos.size() < N) X_pos.emplace_back(X_pos.back()); node.resize(2*N-1, Line()); } // @brief 直線 $y = ax + b$ を集合に加える (直線のインデックス番号を与えてもよい) void insert(Y_Tp a, Y_Tp b, int k=-1) { Line line(a, b, k); node_update(line, 0, N, 0, N, 0); } // @brief 線分 $y = ax + b$ ($x_1 \leq x \leq x_2$) を集合に加える (線分のインデックス番号を与えてもよい) void insert(Y_Tp a, Y_Tp b, X_Tp x1, X_Tp x2, int k=-1) { Line line(a, b, k); int t1 = lower_bound(X_pos.begin(), X_pos.end(), x1) - X_pos.begin(); int t2 = lower_bound(X_pos.begin(), X_pos.end(), x2) - X_pos.begin(); assert(t1 < X_pos.size() and X_pos[t1] == x1); assert(t2 < X_pos.size() and X_pos[t2] == x2); t2++; node_update(line, t1, t2, 0, N, 0); } // @brief $x$ を引数に与え、比較関数 comp により順序が最上となる直線 $f$ における値 $f(x)$ と、その直線のインデックスを返す pair<Y_Tp, int> query_pair(X_Tp x) const { int t = lower_bound(X_pos.begin(), X_pos.end(), x) - X_pos.begin(); assert(t < X_pos.size() and X_pos[t] == x); return search_line(t); } // @brief `query_pair` で値だけ取ってくるバージョン Y_Tp query(X_Tp x) const { return query_pair(x).first; } };
#line 1 "math/math_010_convexhulltrick.cpp" // @brief Convex Hull Trick (Li-Chao Tree) template <typename X_Tp, typename Y_Tp> struct LiChaoTree { private: vector<X_Tp> X_pos; Y_Tp E; function<bool(Y_Tp, Y_Tp)> comp; int N; // @brief Line: 直線のクラス struct Line { bool is_empty; Y_Tp a, b; int index; Line() { is_empty = true; } Line(Y_Tp a_, Y_Tp b_, int index_) : a(a_), b(b_), index(index_) { is_empty = false; } bool empty() const { return is_empty; } Y_Tp f(X_Tp x) const { return a*x + b; } }; vector<Line> node; void node_update(Line line, int t1, int t2, int l, int r, int k) { int mid = (l + r) / 2; if(t2 <= l or r <= t1) return; if(t1 <= l and r <= t2) { if(node[k].empty()) { node[k] = line; return; } if(comp(line.f(X_pos[l]), node[k].f(X_pos[l])) and comp(line.f(X_pos[r-1]), node[k].f(X_pos[r-1]))) return; if(comp(node[k].f(X_pos[l]), line.f(X_pos[l])) and comp(node[k].f(X_pos[r-1]), line.f(X_pos[r-1]))) { node[k] = line; return; } if(r - l == 1) return; if(comp(node[k].f(X_pos[mid]), line.f(X_pos[mid]))) { swap(line, node[k]); } if(comp(node[k].f(X_pos[l]), line.f(X_pos[l]))) { node_update(line, t1, t2, l, mid, 2*k+1); } else { node_update(line, t1, t2, mid, r, 2*k+2); } } else { node_update(line, t1, t2, l, mid, 2*k+1); node_update(line, t1, t2, mid, r, 2*k+2); } } pair<Y_Tp, int> search_line(int t) const { pair<Y_Tp, int> result(E, -1); int l = 0, r = N, k = 0; while(true) { if(!node[k].empty()) { pair<Y_Tp, int> cand(node[k].f(X_pos[t]), node[k].index); if(comp(result.first, cand.first)) result = cand; } if(r - l == 1) break; int mid = (l + r) / 2; if(t < mid) r = mid, k = 2*k + 1; else l = mid, k = 2*k + 2; } return result; } public: // @brief クエリが与えられる座標・単位元・比較関数を渡す LiChaoTree(vector<X_Tp> X_pos_, Y_Tp E_, function<bool(Y_Tp, Y_Tp)> comp_) : X_pos(X_pos_), E(E_), comp(comp_) { sort(X_pos.begin(), X_pos.end()); X_pos.erase(unique(X_pos.begin(), X_pos.end()), X_pos.end()); N = 1; while(N < X_pos.size()) N <<= 1; while(X_pos.size() < N) X_pos.emplace_back(X_pos.back()); node.resize(2*N-1, Line()); } // @brief 直線 $y = ax + b$ を集合に加える (直線のインデックス番号を与えてもよい) void insert(Y_Tp a, Y_Tp b, int k=-1) { Line line(a, b, k); node_update(line, 0, N, 0, N, 0); } // @brief 線分 $y = ax + b$ ($x_1 \leq x \leq x_2$) を集合に加える (線分のインデックス番号を与えてもよい) void insert(Y_Tp a, Y_Tp b, X_Tp x1, X_Tp x2, int k=-1) { Line line(a, b, k); int t1 = lower_bound(X_pos.begin(), X_pos.end(), x1) - X_pos.begin(); int t2 = lower_bound(X_pos.begin(), X_pos.end(), x2) - X_pos.begin(); assert(t1 < X_pos.size() and X_pos[t1] == x1); assert(t2 < X_pos.size() and X_pos[t2] == x2); t2++; node_update(line, t1, t2, 0, N, 0); } // @brief $x$ を引数に与え、比較関数 comp により順序が最上となる直線 $f$ における値 $f(x)$ と、その直線のインデックスを返す pair<Y_Tp, int> query_pair(X_Tp x) const { int t = lower_bound(X_pos.begin(), X_pos.end(), x) - X_pos.begin(); assert(t < X_pos.size() and X_pos[t] == x); return search_line(t); } // @brief `query_pair` で値だけ取ってくるバージョン Y_Tp query(X_Tp x) const { return query_pair(x).first; } };