Convex Hull Trick
コードについての説明
傾きが単調であるような(以下の実装は単調減少しているような) $n$ 個の直線について, 各 $x$ 座標における、 $n$ 個の直線の最小値を効率よく計算するアルゴリズムである.
add する際に最小値を取る可能性が無いような直線は取り除き, またクエリ(最小値を求めたい $x$ 座標)が単調なら前から順に直線を見ていき最小値をこれ以降取らなくなった段階で取り除くということをする.
クエリが単調でない場合についても二分探索をすることで求めたい $x$ 座標について最小値を取る直線が得られるのでそれを用いて最小値を計算すればよい.
(関数)
$add(a,b)$ : 直線 $y=ax+b$ を追加する
$get(x)$ : $x$ での最小値を返す
コード
//f[j](x) = a[j]x + b[j]でaがjの増加に伴い単調減少する場合
//クエリのxが単調でない場合はコメントアウトしたにぶたんの方を用いる
template<typename T> class CHT
{
private:
using ptt = pair<T, T>;
bool check(ptt l1, ptt l2, ptt l3){
return (l2.first-l1.first)*(l3.second-l2.second)>=(l2.second-l1.second)*(l3.first-l2.first);
}
T f(int i, T x){
return lines[i].first * x + lines[i].second;
}
public:
vector<ptt> lines;
int head;
CHT(): head(0){};
void add(T a, T b){
ptt line(a, b);
while((int)lines.size() - head >= 2 && check(*(lines.end()-2), lines.back(), line)){
lines.pop_back();
}
lines.emplace_back(line);
}
T get(T x){
while((int)lines.size() - head >= 2 && f(head, x) >= f(head + 1, x)){
head++;
}
return f(head, x);
// int low = -1, high = lines.size() - 1;
// while (high - low > 1) {
// int mid = (high + low) / 2;
// if(f(mid, x) >= f(mid+1, x)){
// low = mid;
// }else{
// high = mid;
// }
// }
// return f(high, x);
}
};