簡単のため、二分探索の走査範囲を[0,N]とする
二分探索で必要となる情報は、ある値midに対して条件を満たすかどうか(求めたい”境界の値”はmidの左側と右側のどちらの区間に含まれるのか)
midを一段階進めるごとに、境界の値が含まれる区間の長さが半分になっていく(最初の区間を細かくしていく)
Q回の二分探索で見るmidの個数はは高々QlogN
条件を満たすかどうかの判定に、mid一つ当たりX回の計算が必要な場合、最終的にQXlogN回の計算が必要になってしまう
二分探索ごとにX回計算しているのを、一度X回計算した結果を毎回の二分探索に流用することで、計算量をO((Q+X)logN)にしようという話
CODE THANKS FESTIVAL 2017 H
各クエリごとに、二分探索で初めて同じ集合に属した時刻を求める
この問題の場合、条件を満たすかどうかの判定にM回の集合をmergeする操作が必要
愚直に二分探索をすると、M回の計算をしてmidを一つ進めることができる
並列二分探索は、Q個のmidを同時に管理して、M回の計算で各midを同時に一つ進めている
結局並列二分探索が適用できるのは、二分探索ごとに条件判定のための処理が同じとき（条件判定の処理を使い回せるとき）
2017-2018 ACM-ICPC Latin American Regional Programming Contest I
各クエリごとに、二分探索で与えられた頂点の両方が初めてMSTに属した時刻を求める
集合のmergeに対する並列二分探索は永続データ構造で代用可能(roll-backが高速にできるならわざわざ二分探索ごとに初期状態からmergeしていく必要がない)