切片昇順で構築するConvex Hull Trick

問題

最初、 を空集合とする。次の2種類の命令を大量に与えられるので順に実行し、Find 命令の場合は値を出力せよ

• Add(a, b): に ペア を追加する
• Find(x): を求める

オンライン問題、つまりクエリを先読みしない問題とする。
a, b, x は整数 -100000000 <= a, b, x <= 100000000

この問題は Convex Hull Trick と呼ばれる手法で効率的に解くことができる。
[Tutorial] Convex Hull Trick — Geometry being useful - Codeforces
Convex hull trick - PEGWiki
下側凸包の実装に二分探索木が必要になるが、問題に追加の条件があれば vector で実装できることもあるのでここに書く。

切片昇順の場合

追加の条件として Add(a, b) 命令は が昇順で与えられるとする。ここで Find(x) の は 0 以上とすると、凸包の の部分を全て捨てることができ、追加される直線は必ず左端になる。よって vector で実装できる。

convex hull

青い線が vector の中身、赤い線が x が0以上の凸包、灰色の斜線は vector から捨てられた直線。左の図に1本追加した例が右の図になり、普通なら凸包を構成するはずの直線も負の部分は捨てられる。
同様に Find(x) の が負の命令は を捨てたもう一つの凸包を作ればよい。

USACOで出題された。
usaco.org

傾き昇順の場合

追加の条件として Add(a, b) 命令は が昇順で与えられるとする。追加される直線は必ず凸包の右端になるので vector で実装できる。多くのサイトで解説されている。
プログラミングコンテストチャレンジブックでは、傾きが降順の問題が解説されている。

結論

考察をせずに二分探索木の実装を貼るのが良い。