Convex Hull Trick

Convex Hull Trickは、一次関数の集合を保持し、それらのあるx座標における最小値を求めるクエリに効率的に答えるテクニックである。

一般のケース

追加する直線を $ax+b$ とする。

傾きがa以上の直線の中から傾きが最小のものをl1とする。 l2の次に傾きが小さい直線をl2とする。 l1とl2の交点のx座標における値が、ax+bのものがl1,l2のものより小さいなら、 ax+bを加える。

直線を追加したら、新しく不要な直線が発生するので、削除する必要がある。前後それぞれの向きに、不要でない直線が見つかるまで削除していけばいい。

追加した直線の次の直線をl1、さらにその次の直線をl2とする。 l1とl2の交点が直線lより上にあるなら、l1はもう二度と最小値を取らないことがわかる。

xにおける値が直前の直線より小さくなっているようなものの内、最後のものを選ぶ

std::setのlower_boundでは実装できない。平衡二分探索木が必要？

挿入する場所は常に最後尾で、二分探索の必要がないので、２分探索木ではなく単なる配列を使って直線を保持すればいい

最も傾きの大きい直線から順に、xにおける値を調べる。値が下がらなくなるまで調べればいい。