This documentation is automatically generated by competitive-verifier/competitive-verifier
#include "structure/convex-hull-trick/li-chao-tree.hpp"あらかじめ指定した $x$ 座標に対して、直線 $ax+b$ の追加と最小値クエリを効率的に処理するデータ構造。
T: 座標、直線の係数、および計算結果の型LiChaoTree(const vector<T>& x, T INF)
クエリ対象の座標を指定し、直線を含まない状態で初期化する。x は内部で昇順にソートされ、重複する座標は除かれる。
x: クエリ対象の座標。入力時点ではソート済みでなくてもよく、重複を含んでもよいINF: 直線が追加されていないときに返す値INF はすべてのクエリ結果以上T で表現できるvoid update(T a, T b)
直線 $ax+b$ を追加する。
a: 直線の傾きb: 直線の切片T query(int k)
コンストラクタに渡した座標を昇順に並べて重複を除いた列の $k$ 番目の座標における、追加済みの直線の最小値を返す。直線が追加されていない場合は INF を返す。
k: クエリ対象の座標の添字#pragma once
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>
template <typename T>
struct LiChaoTree {
struct Line {
T a, b;
Line(T a, T b) : a(a), b(b) {}
inline T get(T x) const { return a * x + b; }
inline bool over(const Line& b, const T& x) const {
return get(x) < b.get(x);
}
};
std::vector<T> xs;
std::vector<Line> seg;
int sz;
LiChaoTree(const std::vector<T>& x, T INF) : xs(x) {
std::sort(std::begin(xs), std::end(xs));
xs.erase(std::unique(std::begin(xs), std::end(xs)), std::end(xs));
sz = 1;
while (sz < (int)xs.size()) sz <<= 1;
while ((int)xs.size() < sz) xs.push_back(xs.back());
seg.assign(2 * sz - 1, Line(0, INF));
}
void update(Line& x, int k, int l, int r) {
int mid = (l + r) >> 1;
auto latte = x.over(seg[k], xs[l]), malta = x.over(seg[k], xs[mid]);
if (malta) std::swap(seg[k], x);
if (l + 1 >= r)
return;
else if (latte != malta)
update(x, 2 * k + 1, l, mid);
else
update(x, 2 * k + 2, mid, r);
}
void update(T a, T b) { // ax+b
Line l(a, b);
update(l, 0, 0, sz);
}
T query(int k) { // xs[k]
const T x = xs[k];
k += sz - 1;
T ret = seg[k].get(x);
while (k > 0) {
k = (k - 1) >> 1;
ret = std::min(ret, seg[k].get(x));
}
return ret;
}
};
#line 2 "structure/convex-hull-trick/li-chao-tree.hpp"
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>
template <typename T>
struct LiChaoTree {
struct Line {
T a, b;
Line(T a, T b) : a(a), b(b) {}
inline T get(T x) const { return a * x + b; }
inline bool over(const Line& b, const T& x) const {
return get(x) < b.get(x);
}
};
std::vector<T> xs;
std::vector<Line> seg;
int sz;
LiChaoTree(const std::vector<T>& x, T INF) : xs(x) {
std::sort(std::begin(xs), std::end(xs));
xs.erase(std::unique(std::begin(xs), std::end(xs)), std::end(xs));
sz = 1;
while (sz < (int)xs.size()) sz <<= 1;
while ((int)xs.size() < sz) xs.push_back(xs.back());
seg.assign(2 * sz - 1, Line(0, INF));
}
void update(Line& x, int k, int l, int r) {
int mid = (l + r) >> 1;
auto latte = x.over(seg[k], xs[l]), malta = x.over(seg[k], xs[mid]);
if (malta) std::swap(seg[k], x);
if (l + 1 >= r)
return;
else if (latte != malta)
update(x, 2 * k + 1, l, mid);
else
update(x, 2 * k + 2, mid, r);
}
void update(T a, T b) { // ax+b
Line l(a, b);
update(l, 0, 0, sz);
}
T query(int k) { // xs[k]
const T x = xs[k];
k += sz - 1;
T ret = seg[k].get(x);
while (k > 0) {
k = (k - 1) >> 1;
ret = std::min(ret, seg[k].get(x));
}
return ret;
}
};