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$일 때 앞부분의 높이 $$에 있는 을 지운다. 일 때 뒷부분의 높이 에 있는 을 지운다. 그 상태에서 를 출력하고, 방금 지운 가로선을 다시 만든다.

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

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

증명

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

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

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

Solution written by GPT5