並列二分探索 メモ

 

簡単のため、二分探索の走査範囲を[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していく必要がない)