병렬 이분 탐색

동기

각 질의가 "어떤 단조 조건이 처음 참이 되는 시점 \(t\)" 를 묻는 형태라 하자. 예컨대 간선이 시간 순으로 추가되며, 질의 \(q\) 는 "두 정점이 처음 연결되는 시점" 또는 "\(k\)번째 물이 마을에 도달하는 작업 번호" 를 묻는다. 질의 하나당 독립적으로 이분 탐색하면 매번 자료구조를 처음부터 시뮬레이션해야 해 \(O(Q\cdot M\log T)\) 로 폭발한다. 병렬 이분 탐색(Parallel Binary Search) 은 모든 질의의 이분 탐색을 같은 라운드에서 동시에 진행해 시뮬레이션을 공유한다.

핵심 통찰

각 질의 \(q\) 는 현재 후보 구간 \([lo_q, hi_q]\) 를 가지고 그 중점 \(mid_q\) 의 답을 알고 싶어 한다. 서로 다른 질의의 \(mid\) 는 다르지만, 시간축을 한 번 처음부터 끝까지 훑으면서 "지금 시각이 \(mid_q\) 인 질의들"의 판정만 그 순간 처리 하면, 한 번의 전체 시뮬레이션으로 모든 질의의 중점 판정을 끝낼 수 있다.

각 라운드:

1. 모든 활성 질의의 \(mid_q\) 를 계산하고, 시각별 버킷 check[mid_q] 에 질의를 모은다.
2. 자료구조를 시각 1부터 \(T\)까지 한 번 진행하면서, 시각 \(t\) 에 도달하면 check[t] 의 모든 질의를 현재 상태로 판정해 \(lo/hi\) 를 갱신한다.
3. 구간이 모두 한 점이 될 때까지 \(O(\log T)\) 라운드 반복.

복잡도

라운드가 \(O(\log T)\) 개, 라운드마다 전체 시뮬레이션 비용 \(O((M+Q)\,\alpha)\) (\(\alpha\)=자료구조 연산 비용)이므로 전체

$$ O\big((M+Q)\,\alpha\,\log T\big). $$

질의별로 따로 이분하는 것보다 \(\log T\) 만큼이 아니라 질의 개수만큼 이득이 난다(시뮬레이션 공유).

단조성 조건

판정 함수 \(P_q(t)\) 가 \(t\) 에 대해 단조여야 한다(한 번 참이 되면 계속 참). 보통 "간선/작업을 추가만 한다"는 점에서 단조성이 나온다. 추가만 일어나야 자료구조를 매 라운드 깨끗이 재시작하고 앞에서부터 다시 쌓을 수 있다.

언제 쓰나

전형적 구현 (DSU 기반 연결 시점)

간선이 시간 순으로 추가되고, 질의 \(q=(u_q,v_q)\) 가 "두 정점이 처음 같은 집합이 되는 간선 번호"를 묻는 경우.

#include <bits/stdc++.h>
using namespace std;

int n, m, Q;
vector<array<int,2>> edges;            // edges[t] = {u, v}, 1..m번째 간선
vector<array<int,2>> queries;          // queries[q] = {u, v}
vector<int> lo, hi;                    // 각 질의의 답 구간

struct DSU {                           // 롤백 불필요: 매 라운드 새로 만든다
    vector<int> p, r;
    void init(int n){ p.resize(n+1); r.assign(n+1,0); iota(p.begin(),p.end(),0);}
    int find(int x){ return p[x]==x ? x : p[x]=find(p[x]); }
    void uni(int a,int b){ a=find(a);b=find(b); if(a==b)return;
        if(r[a]<r[b])swap(a,b); p[b]=a; if(r[a]==r[b])r[a]++; }
} dsu;

void parallel_binary_search() {
    lo.assign(Q, 1); hi.assign(Q, m + 1);   // m+1 = "끝까지 연결 안 됨"
    while (true) {
        vector<vector<int>> check(m + 1);    // 시각 t에 판정할 질의들
        bool any = false;
        for (int q = 0; q < Q; q++) if (lo[q] < hi[q]) {
            int mid = (lo[q] + hi[q]) / 2;
            check[mid].push_back(q);
            any = true;
        }
        if (!any) break;

        dsu.init(n);
        for (int t = 1; t <= m; t++) {
            dsu.uni(edges[t][0], edges[t][1]);
            for (int q : check[t]) {
                if (dsu.find(queries[q][0]) == dsu.find(queries[q][1]))
                    hi[q] = t;               // 시각 t에 이미 연결 → 더 일찍 가능
                else
                    lo[q] = t + 1;           // 아직 안 됨 → 더 늦게
            }
        }
    }
    // lo[q] == m+1 이면 끝까지 연결되지 않음
}

자주 하는 실수

• 매 라운드 자료구조 초기화 누락. 시각 1부터 다시 쌓아야 한다. 롤백 DSU가 아니라면 반드시 init.
• 버킷 위치. 간선을 추가한 뒤 그 시각의 질의를 판정해야 "시각 \(t\)까지 포함" 의미가 맞는다.
• 상·하한 의미. "처음 참이 되는 시각"을 찾는다면 참일 때 hi=mid, 거짓일 때 lo=mid+1. 경계 정의를 한 번만 정하고 유지한다.
• 답 없음 표현. \(hi\) 의 초기값을 \(m+1\) 로 두어 "끝까지 불가능"을 구분한다.

응용

변형

판정에 세그먼트 트리·펜윅이 필요하면 라운드마다 그 구조를 새로 만들어 시각 순으로 갱신한다. 자료구조에 롤백이 가능하면 "추가/삭제" 가 섞인 더 일반적인 상황도 다룰 수 있으나, 표준 PBS는 추가-단조 가정이 가장 깔끔하다.