Permutations and Queries

2. A coordinate system with one fixed endpoint

First use position $1$ as the endpoint. Let $R$ be the reversal of $[2,N]$. It fixes position $1$ and maps every other position $x$ to $N+2-x$.

The two distances

sum to $N$. Therefore, at least one of them is at least $D$. If $x$ is too close to position $1$ in the current coordinate system, applying $R$ once makes it sufficiently far away.

Treat the state after applying $R$ as another coordinate system. Only the actual position representing each logical position changes. Swapping two actual positions in that coordinate system swaps the corresponding logical positions. One Boolean value is enough to remember whether this coordinate system is reversed.

The construction for endpoint $N$ is symmetric and uses the reversal $[1,N-1]$.

3. A cycle containing the endpoint

Consider a permutation cycle

where $P_{c_i}=c_{i+1}$ and $P_{c_k}=c_1$. Suppose $c_1$ is the current endpoint.

Swap the following pairs of logical positions in order:

These swaps fix every position in the cycle.

Before each swap, if the other position is too close to the endpoint, apply the auxiliary reversal $R$ once. The two positions can then be exchanged with two reversals. The $k-1$ swaps require $2k-2$ reversals. Coordinate-system changes are needed at most once before each swap and at most once more at the end, for at most $k$ changes.

Thus, a cycle of length $k$ containing the endpoint can be processed using at most

reversals.

4. A cycle not containing an endpoint

Choose an initial position $c_1$ of the cycle.

If $c_1\geq L$, reverse $[1,c_1]$. This reversal is allowed and maps logical position $c_1$ to actual position $1$.

If $c_1<L$, reverse $[c_1,N]$. This reversal is also allowed and maps logical position $c_1$ to actual position $N$.

Process the cycle in this coordinate system using the previous construction, and then reverse the initial interval again to restore the original coordinate system. The first and last reversals add two operations, so a cycle of length $k$ needs at most

reversals.

5. Total number of operations and implementation

Cycles of length $1$ require no operation. Process every other cycle independently. The sum of their lengths is at most $N$, so the total number of reversals is at most $3N$.

In the implementation, compute the cycle decomposition of the permutation. For each cycle, maintain the selected endpoint, the initial coordinate transformation, and one Boolean value for the auxiliary reversal. There is no need to simulate the entire array.

The time complexity excluding the printed output is $O(N)$, and the number of printed operations is $O(N)$.

Solution written by GPT5.6