Array Rotation and Queries

Create two distinct vertices $v$ and $-v$ for every integer $v$ from $1$ to $N$. Also create two sentinel vertices $L$ and $R$ for the left and right ends.

For the current sequence $[a_1,a_2,\cdots,a_N]$, store the following undirected edges.

• Connect $L$ with $-a_1$.
• For every $1\leq i<N$, connect $a_i$ with $-a_{i+1}$.
• Connect $a_N$ with $R$.

Every vertex has degree exactly $1$, so its unique neighbor can be stored in an array $\operatorname{mate}$.

If two consecutive sequence values are $u,v$, their adjacency is represented by the edge $\{u,-v\}$. After both reversing and negating that part, the corresponding consecutive values become $-v,-u$. Their edge is $\{-v,u\}$, which is the same undirected edge. Therefore, every edge strictly inside the queried interval remains unchanged.

Let the query endpoints be $x,y$, and define

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

Before the query, the edges $\{-x,\ell\}$ and $\{y,r\}$ exist. Remove them and add

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

These two changes exactly replace the first value $x$ by $-y$ and the last value $y$ by $-x$. Thus, each query changes only four array entries.

To reconstruct the final sequence, start at $L$. Since $\operatorname{mate}(L)=-a_1$, the first value is $-\operatorname{mate}(L)$. If the current value is $v$ and $\operatorname{mate}(v)\neq R$, the next value is $-\operatorname{mate}(v)$.

Initialization and reconstruction take $O(N)$ time, while each query takes $O(1)$ time. The total time complexity is $O(N+Q)$ and the memory complexity is $O(N)$.

Solution written by GPT5.6