並列二分探索

同じ範囲の二分探索を複数回行う問題で、それぞれ個別に二分探索をするのではなく、それぞれの$ 1ステップを同時に進める。

$ Q個のクエリについて、それぞれは$ O(M)の判定を$ \mathrm{log}K回行えば解けるものとする。

これを愚直に行うと$ O(QM\mathrm{log}K)で解くことになるが、

判定問題の部分を他のクエリと同時に行えるなら、$ 1回の判定問題ですべてのクエリを同時に$ 1ステップ進めることができるので、$ O((Q+M)\mathrm{log}K)に改善できる。