이동식 저장소

jh님이 주신 숙제.

익숙한 Union-Find 코드가 보인다. 

주어진 결과값을 이용하여 원래 입력값을 찾아야 하는 문제이다. 딱 봐도 쿼리를 만드는 방법이 매우 많고, 따라서 가장 간단한 방법을 취해야 한다. 코드포스 A~B번 스타일의 문제.

쿼리를 분석해 보자

1번 쿼리는 전형적인 merge 연산이다.

별 볼 일 없는 1번 대신 2번 쿼리에 집중해야 한다. 쿼리가 독특한데, 주어진 원소 v와 같은 집합에 속하는 원소를 아무거나 하나 반환하라고 한다. 아무거나라는 말에 집중하자. 위에서 가장 간단한 방법을 사용해야 한다고 말했는데, 원소 v와 같은 집합에 속하는 원소 중 가장 쉽게 구할 수 있는 원소가 뭘까? 당연히 v다. 즉 가장 쉽게 만들 수 있는 2번 쿼리는 2 v이다.

이 방법을 사용하기로 결정했다면, 원소를 merge하기 전에 모든 2번 쿼리를 출력해야 한다. 왜냐하면 문제에서 주어진 코드는 쿼리 2 v에 대해 v의 부모를 출력하기 때문이다. 2 v의 결과값이 항상 v가 되어야 하므로 초기 상태에서 2번 쿼리를 모두 출력해야 한다.

$1$부터 $N$까지 $N$개의 자연수를 원소로 가지는 $1,2,\cdots ,N$이 있다.

바로 이 초기 상태에서 모든 2번 쿼리를 출력해야 한다. 1번 쿼리는 그 다음이다.

이제 1번 쿼리

1번 쿼리는 조금 복잡하다. 예제 입력 1을 보면서 생각해 보자.

6 7
4 4 4 6 6 6
2
4
6

예제 출력 이미지를 보면, 마지막에 1, 2, 3, 4, 5 모두 6번 부모의 자식임을 알 수 있다. 그런데 출력을 보면 $par(1)=4$이다. 이게 뭘까?

$par[1]$에 $4$가 할당된 이후 다시 할당된 적이 없다는 뜻이다. 즉 $par[par[i]]\ne par[i]$인 경우, $par[i]$가 한번 할당된 후에는 모든 merge 작업이 $par[i]$ 위에서 이루어졌다는 말이다. 말이 조금 어려운데, 트리를 보면서 생각하면 이해하기 쉬울 것이다.

요약하면

1. $i$와 $par[i]$를 merge하기 전에
2. 모든 $i$의 자식들이 $i$로 merge된 후
3. $i$가 $par[i]$에 merge되어야 한다.

$i=par[i]$인 $i$에 대해 위의 재귀 함수를 실행하면 된다.

잠깐

위의 재귀함수가 호출되는 횟수는 $i\ne par[i]$인 $i$의 개수와 같고, 이 수는 $N$보다 작다. 그런데 $N\le 300,000,Q\le 300,000$라는 조건을 잘 보자. $Q\le N$이 보장되지 않는다. 트리를 다 만든 후에도 1번 쿼리를 더 출력해야 할 수도 있다는 뜻이다. 이런 잉여 쿼리는 어떻게 할까?

제한 탭에 보면 아주 중요한 말이 있다.

1번 질의에서 $u,v$는 같을 수 있다.

언뜻 생각해 보면 1 u u 같은 쿼리가 무의미하다고 생각할 수 있다. 그렇지 않다. 위에서 $par[i]!=par[par[i]]$인 경우를 보지 않았는가? 따라서 1 u u가 항상 무의미한 쿼리가 되려면, 이 쿼리가 초기 상태에서 실행되어야 한다.

정리

정리하면 다음과 같다.

1. 2번 쿼리를 출력한 다음
2. (존재한다면) 무의미한 1번 쿼리를 출력한 다음
3. 1번 쿼리를 출력한다. 이때 재귀 호출을 사용하여 트리를 만든다.

간단해 보이지만 함정이 매우 많았던 문제. 골드 3 맞냐?