Solução escrita por Levi Oliveira
Subtarefa 2, 3. $N <= 1000$, $Q <= 1000$.
Para responder essa subtarefa, podemos simular manualmente cada troca. Ao final, imprimimos o valor na $k$-ésima posição do vetor. Para fazer isso, suponha que estamos na posição $i$ e queremos descobrir qual posição devemos trocar com ela.
Inicialmente, perceba que:
- $L+0$ troca com $R-0$;
- $L+1$ troca com $R-1$;
- $L+2$ troca com $R-2$;
e assim por diante.
Sabemos que $L \leq i \leq R$. Portanto, $i-L \geq 0$. Seja $k=i-L$. Isso implica que $i=L+k$. Como vimos pela relação acima, trocamos a posição $L+k$ com a posição $R-k$. Como $L+k=i$ e $k=i-L$, devemos trocar a posição $i$ com: $$R-(i-L)=R+L-i$$. Assim, podemos percorrer o vetor começando em $L$ e avançando para a direita enquanto a posição atual satisfizer:
$$i \leq R+L-i$$
Tomamos esse cuidado para não trocar uma posição que já foi trocada anteriormente. Por exemplo, se trocamos a posição $4$ com a posição $5$, não podemos trocar a posição $5$ com a posição $4$ novamente.
Complexidade: Para cada operação, podemos percorrer até $N$ posições do vetor. Como temos $Q$ operações, a complexidade total é $O(NQ)$.
Subtarefa 4. $Q = 1$
Para responder a essa tarefa, precisamos estender o raciocínio das subtarefas anteriores.
Perceba que, ao realizar uma operação no intervalo $[L,R]$, trocamos a posição $i$ com a posição $R+L-i$. Portanto, depois que o intervalo recebe a operação, o elemento que estava na posição $i$ passa a ocupar a posição $R+L-i$.
Assim, se $K$ estiver dentro do intervalo da query, isto é, se $L \leq K \leq R$, sabemos que a resposta está na posição:
$$R+L-K$$
Caso contrário, ou seja, se $K<L$ ou $K>R$, a resposta continua sendo $K$, pois essa posição não foi afetada pela operação.
Complexidade: $O(1)$.
Problema completo
Para finalizar esse problema, podemos usar a intuição de descobrir “de onde cada posição veio”. Assim, processamos as queries na ordem inversa para descobrir de onde veio o elemento que está atualmente na posição $K$.
Desse modo, suponha que queremos descobrir a origem da posição atual $cur$ e vamos processar a query $[L,R]$.
Se $cur$ estiver dentro desse intervalo, isto é, se $L \leq cur \leq R$, sabemos que o elemento que está nessa posição veio da posição:
$$R+L-cur$$
Portanto, atualizamos $cur$ para $R+L-cur$.
Caso contrário, ou seja, se $cur<L$ ou $cur>R$, essa operação não alterou a posição do elemento que queremos descobrir. Assim, mantemos $cur$ inalterado.
Ao final de todas as queries, $cur$ indicará a posição original do elemento que terminou na posição $K$.