条件付き最大値を対数オーダーで求める

2つの数列Ai, Biが与えられる。Biがxを超えない最大のAiを見つけたい。 単発であれば線形オーダーで見つけられるが、xを変えて繰り返されるので前処理をして対数オーダーにしたい。

(Ai, Bi)を辞書順ソートし、Bj>BiでAj<=Aiであるようなjを取り除く。それらが解になることはないから。 取り除いた列に対して二分探索でBiがxを超えない最大のiを見つければよい。

蟻本p.149