Ladders and Queries

가로선이 $x$번 막대와 $x+1$번 막대를 잇는 것을 $s_x$라 쓰자. 먼저 높이가 증가하는 순서대로

$$s_1,s_2,\cdots,s_{N-1},s_{N-1},\cdots,s_2,s_1$$

을 만든다. 앞부분을 역순으로 한 뒷부분이 이어지므로, 이 사다리는 어느 막대에서 출발해도 같은 막대에 도착한다. 여기까지 $2N-2$번의 $1$번 연산을 사용한다.

목표 $(a,b)$를 처리할 때 $a=b$라면 바로 $2\ a$를 출력한다. 그렇지 않다면 $a>1$일 때 앞부분의 높이 $a-1$에 있는 $s_{a-1}$을 지운다. $b>1$일 때 뒷부분의 높이 $2N-b$에 있는 $s_{b-1}$을 지운다. 그 상태에서 $2\ a$를 출력하고, 방금 지운 가로선을 다시 만든다.

앞부분에서 $s_{a-1}$을 빼면 출발 막대 $a$가 기존의 $1$번 막대 경로로 옮겨진다. 뒷부분에서 $s_{b-1}$을 빼면 그 경로가 $b$번 막대로 이어진다. 따라서 질의의 결과는 $b$이다. 복구 후에는 원래의 항등 사다리가 되므로 다음 목표에도 같은 방법을 쓸 수 있다.

처음에 $2N-2$번, 각 목표마다 최대 $4$번의 $1$번 연산을 사용한다. 총 $6N-2$번 이하이므로 제한을 만족한다. 출력의 길이와 계산 시간은 $O(N)$이다.

증명

가로선 $s_x$는 그 높이를 지나가는 두 막대 $x$와 $x+1$의 경로를 교환한다. 처음 만든 가로선열은 앞쪽 열과 그 역열의 연결이므로 전체 경로의 대응은 항등이다.

앞쪽에서 $s_{a-1}$ 하나를 제거한 효과는 항등 대응에서 $1$과 $a$의 경로를 교환하는 것이다. 뒤쪽에서 $s_{b-1}$ 하나를 제거한 효과는 $1$과 $b$의 도착 막대를 교환하는 것이다. 두 제거를 함께 적용하면 출발 막대 $a$의 경로가 먼저 $1$의 경로로, 이어서 도착 막대 $b$로 이어진다. $a=1$ 또는 $b=1$이면 그쪽 제거는 필요 없다.

모든 질의 뒤에 제거했던 가로선을 복구하므로 다음 질의의 시작 상태는 항상 항등 사다리이다. 따라서 각 질의가 독립적으로 목표를 만족한다.

서브태스크 1에서는 가로선 없이 질의만 출력한다. 서브태스크 2에서는 두 막대를 잇는 가로선 하나를 질의 전후에 토글한다. 서브태스크 3에서는 뒷부분의 가로선만 잠시 지우면 된다. 전체 조건에서는 앞부분과 뒷부분을 모두 사용한다.

Solution written by GPT5