병렬 이분 탐색 (parallel binary search)

 

 

변수 $t$에 의해 참/거짓이 결정되는 문제에 대해, $t$가 정답인 값 $s$ 이하인 경우에는 참(거짓)이다가 해당 값을 넘어가면 거짓(참)인 경우에는 이분 탐색(파라메트릭 서치)을 이용해 문제를 풀 수 있다.

 

이제 오프라인 쿼리의 정답을 찾는 문제를 생각해 보자. 정답의 후보는 1~$N$까지이며 $t=k$인 경우를 확인하기 위해 $O(k)$가 소요된다고 가정해 보자. 쿼리가 $M$개인 경우, 각 쿼리를 이분 탐색하면 $O(MN\log N)$이 걸릴 것이다. 오프라인 쿼리의 특성을 생각해서, 한번에 1~N까지 스위핑 탐색하여 답을 구할 수도 있는데 이때에는 $O(MN)$이 걸린다. 병렬 이분 탐색(pbs)은 두 아이디어를 합친 방법으로, 한 번의 스위핑으로 모든 오프라인 쿼리의 이분 탐색의 한 단계를 진행시키는 방식으로 문제를 해결한다.

 

 

병렬 이분 탐색

각 쿼리들의 이분 탐색 구간을 저장하는 배열 $L[i]$와 $R[i]$를 정의하고, 다음과 같은 방식으로 이분 탐색을 수행한다.

 

• 이미 탐색이 끝난 쿼리는 제외하고, $mtoi[(L[i] + R[i]) // 2]$에 쿼리 인덱스 $i$를 저장해 둔다.
• 1~$N$까지 스위핑하면서 $mtoi$에 들어 있는 쿼리를 처리한다. 기존 이분 탐색과 마찬가지로 결과에 따라서 $L$이나 $R$을 업데이트 해주면 된다.

$mtoi$에는 최대 $M$개의 값들만 들어 있으므로, $O((N \times T_{sweeping} + M \times T_{query})\log N )$만에 문제를 해결할 수 있다.

L = [0]*M; R = [N]*M
ans = [-1]*M
for _ in range(20):
    mtoi = [[] for _ in range(N+1)]
    for i in range(M):
        if L[i] <= R[i]: mtoi[(L[i]+R[i])//2].append(i)
    
    for t in range(1, N+1):
        # sweeping
        
        for i in mtoi[t]:
            # res := (result of query[i])
            
            if res:
                ans[i] = t
                R[i] = t - 1
            else:
                L[i] = t + 1

 

 

크루스칼의 공(BOJ 1396)은 크루스칼 알고리즘으로 union-find를 수행해 현재 온도 $t$에서의 이동 가능 여부를 판단해 주면 된다. 유성(BOJ 8217)은 구간 업데이트 + 점 쿼리를 요구하므로 lazy seg를 사용하거나 차분 배열 트릭을 활용한 풀이가 가능하다.