BOJ 34226 그래프와 연결성 쿼리

https://youtu.be/2UM2Ck7zyDI?si=1XtOfbLfKCm79S3d

 

https://www.acmicpc.net/problem/34226

2025 숭고한 G번 문제다. 대회 때 못풀었기에 업솔빙을 해보자.

 

쿼리마다 $L_q$번째 간선부터 $R_q$번째 간선까지 남겼을 때 그래프의 연결성을 관리해주면 된다.

쿼리를 해결하는 자명한 자료구조가 없어보이니, 루트분할을 생각해보자. 모스같은걸 한다 했을 때, 간선 추가가 있을 때 연결성 관리는 유니온 파인드로 해줄 수 있다. 간선 삭제는 어떻게 할 수 있을까? 내가 아는 방법은 두가지가 있는데,

1) 가장 최근에 한 업데이트를 제거하는 방법. 이는 스택에 유파에서 바뀐 정보들 ($\mathcal{O}(1)$)을 저장해주면 된다.
2) Queue undo trick. 잘은 모르지만 업데이트 삭제를 queue처럼 FIFO스타일로 해줄 수 있다고 한다.

 

모스를 하기 위에선 양쪽 끝 포인터를 계속 옮겨주어야 하기에, 이 문제에선 적용하기 힘들다. 본 대회땐 여기까지 생각하고 다른 문제로 넘어갔다.

 

$[1, M]$ 구간을 $B$크기의 구간들로 쪼개자. $k$번째 구간은 $[B \cdot (k - 1) + 1, B \cdot k]$이다. 이제 쿼리의 왼쪽 끝 $L_q$가 같은 구간에 속하는 애들끼리 같이 처리해겠다.

 

쿼리를 $R_q < B \cdot k$와 $R_q \geq B$ 두가지로 분류해보자. 전자는 구간의 길이가 짧기에 나이브하게 유파에 추가해주는 것으로 $\mathcal{O}(B \log N)$시간에 처리해줄 수 있다.

 

후자에 대해 생각해보자. $R_q$를 증가하는 순서대로 보면, $[B \cdot k, R_q]$구간에 대한 유파를 관리해줄 수 있다. 이제 각 쿼리마다 $[L_q, B \cdot k)$에 대한 업데이트를 유파에 추가해준 후 롤백해주는 것으로 해결해줄 수 있다. 왼쪽 부분을 추가해주는 것은 $\mathcal{O}(B \log N)$ 시간에 가능하고, 오른쪽 부분을 추가해주는 것은 각 버킷마다 $\mathcal{O}(M \log N)$ 시간에 처리해줄 수 있다.

 

총 $\mathcal{O}(QB \log N + \frac{M^2}{B} \log N)$ 시간에 문제를 해결할 수 있다. $B = \sqrt M$으로 두면, $\mathcal{O} ((M + Q) \sqrt M \log N)$ 시간에 문제를 해결 가능하다.