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

2つの数列Ai, Biが与えられる。Biがxを超えない最大のAiを見つけたい。

単発であれば線形オーダーで見つけられるが、xを変えて繰り返されるので前処理をして対数オーダーにしたい。

(Ai, Bi)を辞書順ソートし、Bj>BiでAj<=Aiであるようなjを取り除く。それらが解になることはないから。

https://gyazo.com/e98e4afca708b1d6ecc8f4325e03405f

取り除いた列に対して二分探索でBiがxを超えない最大のiを見つければよい。