수직선상에 깃발 $N$개를 놓되, $i$번째 깃발은 $x_i$ 또는 $y_i$에 놓아야 한다. 이 때 깃발들 사이의 최소 거리의 최댓값을 구하는 문제이다. 문제 링크
Solution sketch
일단 파라메트릭 + 2-SAT을 해야 한다는 것 까지는 자명한 관찰이다. 즉, “가장 가까이 있는 깃발이 $d$ 이상 떨어져 있게 할 수 있는가?”에 관한 문제를 풀자. 그런데 2-SAT에 사용할 그래프 에지를 단순하게 만들면 $O(N^2)$개가 된다.
Idea 1. 2-SAT Segment Tree
편의상 $x$좌표들을 정렬된 순서대로 $p_{1}, p_{2}, \cdots, $라 두자. 앞으로 특별한 말이 없으면 “$i$번째 위치…”와 같은 말은 모두 $p_{i}$로 해석하면 된다.
Segment tree를 하나 빌드하는데, [s,e]의 노드는 “[s,e]번 위치에는 전부 깃발이 놓이지 않는다"라는 명제로 해석한다. [s,e] → [s,m] && [s,e] → [m+1,e]만 간선을 통해 강제하면 이 트리의 노드들을 자유롭게 쓸 수 있다.
Idea 2. Interval update
$i$번째 위치에 깃발이 놓이는 상황을 생각하면, $(p_{i}-d, p_{i}+d)$에는 깃발이 놓일 수 없다. 따라서 해당 구간의 양 끝에 해당하는 인덱스 L, R을 lower/upper_bound로 결정해 주고, 세그트리에 update(L, i-1); update(i+1, R); 쿼리를 날려주자.
update(A, B) 쿼리 내부는 세그트리의 구간 업데이트와 비슷하게 생겼다. 이미 세그트리를 만드는 과정에서 리프들까지 정보가 전달되므로, [s,e]가 [A, B]에 포함되면 [s,e]에 해당하는 노드에 간선을 잇고 빠져나오면 된다.
Analysis
세그트리는 “깃발이 없는” 쪽에만 만들면 충분하다. 여기서 노드가 $8N$개 정도 필요하다.
“깃발이 있다"를 표현하는 노드가 $2N$개 정도. 따라서 2-SAT에 들어가는 노드 개수는 약 $10N$개이다.
매번 간선이 $O(N\log N)$개씩 나오니까, 파라메트릭까지 합치면 $O(N\log N\log X)$ 시간과 $O(N\log N)$ 메모리로 문제를 해결할 수 있다.