순열과 쿼리

$D=\left\lceil\cfrac{N}{2}\right\rceil$, $L=D-1$이라 하자. 허용되는 구간의 최소 길이는 $L$이다.

1. 멀리 떨어진 두 위치의 교환

$x<y$이고 $y-x\geq D$라 하자. 다음 두 구간을 차례대로 뒤집는다.

$[x,y]$ $[x+1,y-1]$

첫 번째 뒤집기는 양 끝의 원소를 서로 바꾸고 내부 구간의 순서를 뒤집는다. 두 번째 뒤집기는 내부 구간만 원래 순서로 되돌린다. 따라서 결과적으로 $x$번 위치와 $y$번 위치의 원소만 교환된다.

두 번째 구간의 길이는 $y-x-1\geq D-1=L$이므로 두 뒤집기는 모두 허용된다. $N=2$이고 두 위치가 인접한 경우에는 $[x,y]$만 뒤집으면 된다.

2. 한쪽 끝점을 고정한 좌표계

먼저 $1$번 위치를 끝점으로 사용한다고 하자. 구간 $[2,N]$을 뒤집는 변환을 $R$이라 하자. $R$은 $1$번 위치를 고정하고, 나머지 위치 $x$를 $N+2-x$로 보낸다.

두 거리

$$x-1,\qquad N+1-x$$

의 합은 $N$이다. 따라서 둘 중 하나는 $D$ 이상이다. 현재 좌표계에서 $x$가 $1$번 위치와 가깝다면 $R$을 한 번 적용한 뒤에는 충분히 멀어진다.

$R$을 적용한 상태를 하나의 좌표계로 생각한다. 논리적인 위치 $i$가 실제 배열의 어느 위치에 있는지만 바뀌며, 그 좌표계에서 두 실제 위치를 교환하면 대응하는 두 논리적 위치가 교환된다. 좌표계가 뒤집혀 있는지는 불리언 값 하나로 관리할 수 있다.

$N$번 위치를 끝점으로 사용할 때도 대칭적으로 구간 $[1,N-1]$을 사용한다.

3. 끝점을 포함하는 순환

순열의 순환 하나가

$$(c_1,c_2,\cdots,c_k)$$

이고 $P_{c_i}=c_{i+1}$, $P_{c_k}=c_1$이라 하자. $c_1$이 현재 끝점이라고 하자.

논리적인 위치쌍

$$(c_1,c_2),(c_1,c_3),\cdots,(c_1,c_k)$$

를 차례대로 교환하면 이 순환의 모든 위치가 고정된다.

각 교환 직전에 상대 위치가 끝점과 가깝다면 보조 뒤집기 $R$을 한 번 적용한다. 그 후 두 번의 뒤집기로 두 위치를 교환할 수 있다. $k-1$번의 교환에는 $2k-2$번의 뒤집기가 필요하다. 좌표계 전환은 각 교환 전 최대 한 번, 마지막 복구에 최대 한 번 필요하므로 총 $k$번 이하이다.

따라서 끝점을 포함하는 길이 $k$의 순환은 최대

$$(2k-2)+k=3k-2$$

번의 뒤집기로 처리할 수 있다.

4. 끝점을 포함하지 않는 순환

순환의 시작 위치를 $c_1$로 잡는다.

$c_1\geq L$이면 $[1,c_1]$을 뒤집는다. 이 뒤집기는 허용되며, 논리적인 위치 $c_1$을 실제 $1$번 위치로 보낸다.

$c_1<L$이면 $[c_1,N]$을 뒤집는다. 이 뒤집기도 허용되며, 논리적인 위치 $c_1$을 실제 $N$번 위치로 보낸다.

이 좌표계에서 앞의 방법으로 순환을 처리한 뒤, 처음 사용한 구간을 다시 뒤집어 원래 좌표계로 돌아온다. 처음과 마지막에 뒤집기 한 번씩이 추가되므로 길이 $k$의 순환은 최대

$$1+(3k-2)+1=3k$$

번의 뒤집기로 처리된다.

5. 전체 횟수와 구현

길이가 $1$인 순환에는 연산이 필요하지 않다. 나머지 순환을 각각 위 방법으로 처리한다. 각 순환의 길이를 모두 합하면 $N$ 이하이므로 전체 뒤집기 횟수는 $3N$ 이하이다.

구현에서는 순열의 순환 분해를 구한다. 각 순환에 대해 현재 끝점, 최초 좌표계 변환, 보조 뒤집기 적용 여부만 관리하면서 연산을 출력한다. 배열을 실제로 뒤집어 가며 시뮬레이션할 필요는 없다.

시간 복잡도는 출력 연산을 제외하면 $O(N)$이고, 출력되는 연산 수는 $O(N)$이다.

Solution written by GPT5.6