Skip to content

BOJ 22906 장난감 오렌지 만들기

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

서브태스크 1

사실 이 문제는 그래프로 모델링할 수 있습니다. 연결 고리의 색이 a, b인 블록은 정점 a와 b를 잇는 간선으로 보면, 각 쿼리는 정확히 l번째부터 r번째까지의 간선만으로 만들어진 그래프를 최소 개수의 회로(circuit)로 분할하는 문제가 됩니다.

모든 정점의 번호가 1 이상 2N 이하라고 합시다. 아니라면 [[좌표 압축]]을 하면 됩니다.

l번째부터 r번째까지의 간선만 이은 다음, 각각의 연결 요소에 대해 문제를 풀고 합치면 답을 구할 수 있습니다. 연결 요소에 간선이 없다면 최소 회로는 0개입니다. 차수가 홀수인 정점이 하나라도 있다면 회로로 분할할 수 없습니다. 그렇지 않다면 [[오일러 회로]]를 만들 수 있기 때문에 최소 회로는 1개입니다.

따라서, 쿼리의 답은 차수가 홀수인 정점이 하나라도 있다면 -1, 아니면 간선이 최소 하나인 연결 요소의 개수와 같습니다. 쿼리가 들어올 때마다 DFS를 하면 O(QN)이 됩니다. 실제로 오일러 회로를 만들 필요는 없습니다.

서브태스크 2

차수가 홀수인 정점이 존재하는지를 빠르게 알아내야 합니다.

수열 a1, b1, a2, b2, ..., aN, bN을 생각해 봅시다. 그러면 2l번째부터 2r+1번째까지 보았을 때, 정확히 홀수 개 들어있는 수가 존재하는지 판별하는 문제가 됩니다.

"같은 수가 짝수 개"라는 키워드에서 XOR을 생각할 수 있습니다. 각 정점마다 랜덤으로 64비트 정수 "레이블"을 부여한 다음, 2l번째부터 2r+1번째까지 정점의 레이블 값을 XOR합시다. 이 값이 0이라면, 1에 가까운 확률로 모든 수가 짝수 개씩 존재합니다. 0이 아니라면, 무조건 홀수 개 들어있는 수가 적어도 하나 존재합니다.

수열의 값이 중간에 바뀌지 않으므로, 구간 XOR은 [[누적 합]]으로 쿼리 당 O(1), 총 O(N+Q)에 구할 수 있습니다.

서브태스크 3

서브태스크 2의 방법으로 답이 -1인지 아닌지는 알 수 있습니다. 이제 답이 -1이 아니면 "간선이 최소 하나인 연결 요소의 개수"를 세야 되는데, 일단 간선이 최소 하나라는 조건은 무시하고 그냥 연결 요소의 개수를 다 세어 봅시다. 그런데 사실 이것도 어렵기 때문에, 이걸 또 두 서브태스크로 나눠서 생각해야 합니다.

  • Easy 버전: 모든 쿼리의 l이 같습니다.
  • Hard 버전: 추가 제약 조건이 없습니다.

연결 요소의 개수 (Easy)

우선 모든 쿼리의 l이 같다고 합시다. 그러면 모든 쿼리를 r에 대한 오름차순으로 정렬한 후 [[분리 집합]]으로 풀 수 있습니다. l번째 간선부터 차례대로, 간선이 두 연결 요소 사이를 이을 때마다, 그 둘을 합쳐 주고 개수를 1 줄이면 됩니다.

사실 쿼리를 정렬할 필요도 없습니다. 실제로 연결 요소를 합치는 데 사용된 간선들을 모아 놓으면, [l, r]에 대한 답은 n - (번호가 r 이하인 간선의 개수)입니다.

연결 요소의 개수 (Hard)

실제로 연결 요소를 합치는 데 사용된 간선들은 스패닝 포레스트를 이룰 것입니다. l번째 간선에서부터 위 과정으로 만들어진 스패닝 포레스트를 F(l)이라고 합시다.

F(l)이 있을 때, F(l-1)은 어떻게 구할 수 있을까요? 우선 l-1번째 간선을 볼 때는 아무 간선도 없으므로, F(l)에다가 l-1번째 간선을 추가해 봅시다. 만약 l-1번째 간선이 F(l)의 서로 다른 연결 요소를 이었다면, 이게 그냥 F(l-1)입니다.

l-1번째 간선이 F(l)의 하나의 연결 요소 안에 놓여 있는 경우가 문제입니다. l-1번째 간선이 정점 a와 b를 잇는다고 합시다. 그러면 F(l-1)을 만드는 과정은 F(l)과 거의 같은데, a와 b가 한 연결 요소로 모이는 시점이 앞당겨집니다. 그리고 F(l)에서 a와 b 사이의 경로 중 가장 마지막으로 추가된 간선이 무시됩니다. 나머지 간선은 변화가 없습니다.

따라서 F(l-1)은, F(l)을 구한 다음, a와 b 사이의 경로 중 번호가 가장 큰 간선을 제거하고 a와 b를 바로 이으면 구할 수 있습니다. 링크-컷 트리로 모든 F(i)를 O(NlogN)에 구할 수 있습니다.

쿼리 [l, r]에 대한 답은 n - (F(l)에서 번호가 r 이하인 간선의 개수)입니다. 쿼리를 l에 대한 내림차순으로 정렬하고, F(n), F(n-1), ..., F(1)을 차례대로 구하면서 모든 쿼리의 답을 펜윅 트리로 O(Q+NlogN)에 구할 수 있습니다.

간선이 있는 연결 요소의 개수

실제 답은 (차수가 1 이상인 정점의 개수) - (F(l)에서 번호가 r 이하인 간선의 개수)이기 때문에, 이제 차수가 1 이상인 정점의 개수를 구해야 합니다.

이 값은 수열 a1, b1, a2, b2, ..., aN, bN의 2l번째부터 2r+1번째까지의 수 중 서로 다른 수의 개수와 같습니다. BOJ 14897 서로 다른 수와 쿼리 1의 풀이를 그대로 쓰면 됩니다. Mo's algorithm 말고 오프라인 + 펜윅 트리를 권장합니다.

BOJ14898 서로 다른 수와 쿼리 2의 풀이인 온라인 + [[머지 소트 트리]]를 써도 시간 내에 돌아갑니다.