https://www.acmicpc.net/problem/20930
문제요약
-
선분으로 된 우주정거장이 있음
-
우주선은
- 우주정거장 내부를 이동하거나
- x축으로 이동하거나
- y축으로 이동하거나
-
우주정거장 a에서 b를 이동할 수 있는지 쿼리 수행
-
N <= 200000, Q <= 200000
접근법
- 갈 수 있는 우주정거장끼리 연결 후 그래프 탐색을 수행하면 시간복잡도...
- disjoint set을 이용하면 a, b가 연결되어있는지는 파악할 수 있을 것 같음
- 우주정거장간 연결관계는?
- x 좌표만 생각했을때, 스위핑을 하면서 살펴보면 범위 안에 있는 것들은 서로 연결된 것이라고 볼 수 있음(선분이 겹치는 문제, (시작, 끝)이 주어질때 몇 개가 유지되고 있는지 파악하는 문제)
- 들어가고, 나가고 판단을 해서 현재 유효한 정거장을 유지시켜줄 수 있을 것 같음 => buf에 쌓음
- 새로운 정거장이 유효해지면, 기존의 정거장중에 아무거나와 연결(=union find)해주면 같은 그룹으로 묶이겠음
- 기존 정거장이 나가면 일단 나가는 처리를 하고, 나중에 이용할때 해당 처리 상태를 봐서 처리할 수 있겠음 => buf에서 바로 빼면 좋겠으나, 아직 유효한 것들이 있으면 그냥 내버려두고 나중에 빼도 됨
- y축에 대해서도 동일한 처리
newbieski