BOJ 16793 Collapse

JOI Open Contest 2018 #3 崖崩れ(Collapse)

 

 

문제 설명

 

정점 $1$부터 정점 $N$까지 $N$개의 정점이 있다.

$i$번째 날에는 하나의 간선을 추가하거나 삭제한다.

다음과 같은 쿼리가 주어진다.

• $W$ $P$ : $W$번째 날에 $P$ 이하의 정점과 $P + 1$ 이상의 정점을 서로 잇는 간선을 모두 삭제했을때, 정점들의 총 컴포넌트의 수를 구하여야 한다.

 

 

Solution

 

정점들의 컨포넌트를 관리하는 대표적인 방법으로는 Union & Find가 있다.

그러나, Union & Find는 간선을 추가된 순서의 역순으로만 삭제할 수 있다.

또한, 구간 $[k, k+1]$을 포함하는 모든 간선을 삭제할 경우 최악의 경우 $O(C)$이므로시간이 매우 오래 걸린다.

 

전체 일수를 R개씩 쪼개자.

날짜에 대한 구간 $[s, e]$에 대하여 문제를 해결한다.

이미 추가되어 구간 $[s, e]$에서 변경사항이 없는 간선을 집합 A, $[s, e]$에서 변경사항이있는 간선을 집합 B라고 정의한다.

정점 $1$부터 $N$까지 차례대로 보자.

• 집합 $A$에 있는 간선 $(u, v)$($u < v$)에 대하여, 정점 $v$를 볼 때 $(u, v)$를 Union Find에삽입한다.
• $W \in [s, e]$인 쿼리 $(W, P)$에 대하여, 정점 $P$를 볼 때 집합 $B$에 있는 간선 중 $W$일차 이전에 존재하는 간선을 모두 추가해 주고 현재 컴포넌트의 수를 구한다.

 

위의 방식으로 쿼리 $(W, P)$의 정점 구간 $[1, W]$에서의 답을 구할 수 있다.

구간 $[W+1, N]$에서의 답은 정점의 순서를 모두 뒤집어서 같은 방식으로 구할 수 있다.

 

 

비슷한 아이디어를 사용하는 문제로는 APIO 2019 #2 다리 문제가 있다.