세 순열과 쿼리

두 값 $x,y$에 대하여, 세 순열 중 적어도 두 순열에서 $x$가 $y$보다 앞에 나오면 $x \to y$라는 방향을 두자. 모든 두 값 사이에는 정확히 한 방향이 정해지므로 이는 토너먼트이다. 좋은 순열이 존재한다는 것은 이 토너먼트의 모든 간선 방향과 일치하는 선형 순서가 존재한다는 뜻이고, 이는 토너먼트가 추이적이라는 것과 동치이다.

각 값 $x$에 대해 다음 값을 정의하자.

$$d[x]=\#\{y:\text{세 순열 중 적어도 두 순열에서 }y\text{가 }x\text{보다 앞에 나온다}\}.$$

즉, $d[x]$는 위 토너먼트에서 $x$의 진입 차수이다.

추이적인 토너먼트의 진입 차수들은 정확히 $0,1,\cdots,N-1$이다. 반대로 모든 $d[x]$가 서로 다르면 각 값이 $0$ 이상 $N-1$ 이하이므로 진입 차수 집합은 정확히 $\{0,1,\cdots,N-1\}$이다. 진입 차수가 $0$인 정점은 모든 다른 정점보다 앞에 놓여야 한다. 이 정점을 제거하면 남은 토너먼트의 진입 차수도 다시 $0,1,\cdots,N-2$가 되므로 귀납적으로 토너먼트는 추이적이다. 따라서 좋은 순열이 존재하는 필요충분조건은 모든 $d[x]$가 서로 다른 것이다.

초기 $d[x]$를 빠르게 구해야 한다. 순열 $u$에서 값 $x$의 위치를 $\operatorname{pos}_u[x]$라고 하자. 두 순열 $u,v$에 대해

$$C_{uv}[x]=\#\{y:\operatorname{pos}_u[y]<\operatorname{pos}_u[x],\ \operatorname{pos}_v[y]<\operatorname{pos}_v[x]\}$$

로 두고, 세 순열 모두에서 앞서는 값의 수를 $C_{pqr}[x]$라고 하자. 어떤 $y$가 세 순열 중 정확히 $k$개에서 $x$보다 앞선다고 하면 $C_{pq}+C_{pr}+C_{qr}$에는 $\binom{k}{2}$번, $C_{pqr}$에는 $k=3$일 때 한 번 포함된다. 따라서

$$d[x]=C_{pq}[x]+C_{pr}[x]+C_{qr}[x]-2C_{pqr}[x].$$

각 $C_{uv}$는 한 순열의 순서대로 훑으면서 다른 순열의 위치를 Fenwick tree에 넣으면 $O(N\log N)$에 구할 수 있다. $C_{pqr}$는 세 위치를 좌표로 보는 3차원 dominance counting이다. $p$의 위치 순서로 정렬한 뒤 CDQ divide and conquer와 Fenwick tree를 사용하면 $O(N\log^2 N)$에 모든 값을 구할 수 있다.

이제 쿼리를 보자. 현재 선택된 순열에서 서로 인접한 두 값이 $x,y$이고, swap 전에는 $x$가 $y$보다 앞에 있다고 하자. 인접한 두 원소를 바꾸면 그 순열 안에서 상대적인 순서가 바뀌는 쌍은 $(x,y)$ 하나뿐이다. 따라서 다수결 토너먼트에서도 바뀔 수 있는 간선은 $x,y$ 사이의 간선 하나뿐이다.

나머지 두 순열에서 $x,y$의 순서가 같다면 다수결 결과는 선택된 순열과 관계없이 이미 정해져 있으므로 아무 변화가 없다. 나머지 두 순열에서 $x,y$의 순서가 서로 다르다면 swap 전에는 $x\to y$, swap 후에는 $y\to x$가 된다. 그러므로 이 경우에만

$$d[x]\mathrel{+}=1,\qquad d[y]\mathrel{-}=1$$

로 갱신하면 된다.

각 가능한 진입 차수 $0,1,\cdots,N-1$의 등장 횟수를 유지하자. 등장 횟수가 $2$ 이상인 값의 개수를 함께 관리하면, 그 개수가 $0$일 때 그리고 그때에만 모든 $d[x]$가 서로 다르다. 한 쿼리에서 최대 두 개의 $d$만 바뀌므로 이 부분은 $O(1)$이다. 세 순열의 현재 위치 배열도 swap과 함께 갱신하면 나머지 두 순열이 서로 같은 순서를 가지는지 $O(1)$에 판정할 수 있다.

초기화 시간복잡도는 $O(N\log^2 N)$, 각 쿼리는 $O(1)$이다. 전체 시간복잡도는 $O(N\log^2 N+M)$이고, 메모리복잡도는 $O(N)$이다.

Solution written by GPT5.6