배열 회전과 쿼리

각 정수 $v$에 대해 서로 다른 두 정점 $v$와 $-v$를 만든다. 또한 왼쪽 끝을 나타내는 정점 $L$과 오른쪽 끝을 나타내는 정점 $R$을 만든다.

현재 수열이 $[a_1,a_2,\cdots,a_N]$일 때 다음 무방향 연결을 저장한다.

• $L$과 $-a_1$을 연결한다.
• 각 $1\leq i<N$에 대해 $a_i$와 $-a_{i+1}$을 연결한다.
• $a_N$과 $R$을 연결한다.

모든 정점의 차수는 정확히 $1$이므로, 각 정점의 유일한 이웃을 배열 $\operatorname{mate}$에 저장할 수 있다.

수열에서 서로 이웃한 두 값이 $u,v$라면 이 둘은 연결 $\{u,-v\}$로 표현된다. 쿼리로 이 두 값의 순서가 뒤집히고 부호도 바뀌면 새 인접쌍은 $-v,-u$가 된다. 이 인접쌍을 표현하는 연결은 $\{-v,u\}$이므로 기존 연결과 같다. 따라서 쿼리 구간 내부의 연결은 하나도 바꿀 필요가 없다.

쿼리의 양 끝을 $x,y$라 하자. 다음 두 값을 구한다.

$$\ell=\operatorname{mate}(-x),\qquad r=\operatorname{mate}(y).$$

쿼리 전에는 연결 $\{-x,\ell\}$과 $\{y,r\}$이 존재한다. 이 두 연결을 지우고 다음 두 연결을 추가한다.

$$\{\ell,y\},\qquad \{-x,r\}.$$

이는 구간의 첫 원소가 $x$에서 $-y$로, 마지막 원소가 $y$에서 $-x$로 바뀌는 것을 정확히 표현한다. 각 쿼리는 배열 원소 네 개를 갱신하는 것으로 처리된다.

최종 수열은 $L$에서 시작하여 복원한다. $\operatorname{mate}(L)=-a_1$이므로 첫 원소는 $-\operatorname{mate}(L)$이다. 현재 원소가 $v$이고 $\operatorname{mate}(v)\neq R$이면 다음 원소는 $-\operatorname{mate}(v)$이다.

초기화와 최종 복원은 $O(N)$, 각 쿼리는 $O(1)$이다. 전체 시간 복잡도는 $O(N+Q)$이고, 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.6