BOJ 33971 비전 마법사 지환

먼저, 배열을 XOR 차분 배열로 바꾸면 목표 배열과 쿼리가 다음과 같이 바뀝니다.

• 시작 상태는 모두 0입니다.
• 목표 상태는 첫 칸이 1이고 나머지는 모두 0입니다.
• $i$번째 마법진에 대해, 마력을 $A$만큼 소모하면 $l_i$와 $r_i+1$번째 칸의 값을 뒤집습니다.
• 마력을 $B$만큼 소모하면 첫 칸과 $l_i$와 $r_i+1$번째 칸의 값을 뒤집습니다.
• 이때 $r_i+1 > N$이면 뒤집지 않고, $l_i = 1$일 경우 첫 칸을 두 번 뒤집는 것은 뒤집지 않는 것과 같습니다.

모든 쿼리는 첫 칸을 제외하고 최소 0개, 최대 2개의 칸을 뒤집게 됨을 알 수 있습니다.

첫 칸을 제외하고 아무것도 뒤집지 않는 경우는 $(l_i, r_i) = (1, N)$인 경우로, 이를 이용하면 마력을 정확히 $A$만큼 써서 모든 칸을 뒤집을 수 있습니다. (단, $A > B$일 수 있으므로, 다른 가능성도 모두 고려한 뒤 모든 가능성 중 최솟값을 출력해야 합니다.)

그 외의 경우, 다음의 관찰을 할 수 있습니다.

• $A$를 $B$로, 또는 $B$를 $A$로 바꿔서 첫 칸을 뒤집은 횟수의 홀짝을 바꿀 수 있습니다. 따라서, $A$와 $B$ 중 작은 것을 사용하여 첫 칸을 제외한 모든 칸을 0으로 만들고, 이때 첫 칸을 뒤집은 횟수가 짝수라면 $|A-B|$의 추가 마력을 사용하면 목표를 달성할 수 있습니다.
• 하나를 뒤집는 쿼리를 사용한다면, 같은 칸 하나만 뒤집는 다른 쿼리를 사용하거나, 그 칸을 포함해서 두 칸을 뒤집는 쿼리를 사용해야 합니다. 후자의 경우 이를 반복하다가 결국 남은 하나를 뒤집는 쿼리를 사용해야 합니다. 이는 두 칸을 뒤집는 쿼리들을 두 칸을 잇는 간선이라고 생각했을 때, 양끝 칸을 잇는 경로가 됩니다.
• 하나를 뒤집는 쿼리를 사용하지 않는다면, 같은 그래프에서 사이클을 찾으면 됩니다.

두 경우 모두 BFS를 이용한 최단 거리를 구하는 것으로 각각의 경우에 대한 최소 비용을 구할 수 있습니다. 이때, 경로 상에서 첫 칸이 뒤집어진 횟수의 홀짝이 다르면 별도의 상태로 생각해야 합니다. 이는 쿼리를 많이 썼지만 홀수 번 뒤집는 경우가 적게 쓰지만 짝수 번 뒤집는 경우보다 비용이 적을 수 있기 때문입니다.

첫 번째 경우는 다음과 같이 처리합니다.

• 하나를 뒤집는 쿼리들을 모두 모아 놓습니다.
• 각각의 쿼리에 대해, 그 점을 시작점으로 하고 나머지 모든 점을 끝점으로 하는 BFS를 수행한 뒤, 하나를 뒤집는 쿼리들 중에서 자기 자신을 제외한 것에 대해 경로상에서 첫 칸의 홀짝에 따라 최소 비용을 계산합니다.

두 번째 경우는 다음과 같이 처리합니다.

• 두 개를 뒤집는 쿼리 각각에 대해, 나머지 쿼리들로 이루어진 그래프 위에서 한쪽 점을 시작점으로 하고 반대쪽 점을 끝점으로 하는 BFS를 수행한 뒤, 경로상에서 첫 칸의 홀짝에 따라 최소 비용을 계산합니다.

이렇게 하면 각 경우 모두 $\mathcal{O}(NM)$에 해결할 수 있습니다.

같은 쿼리가 여러 번 등장하는 입력에 주의하여 구현합니다.