Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 250 C問題 Adjacent Swaps

AtCoder ABC ABC250 C問題 300 pts

問題

提出解答

問題の概要

長さ $N$ の整数列 $A=(A_i)_{i=1}^N$ がある. 最初, $A_i=i$ である.

$q=1,2, \dots, Q$ の順に以下のようにして $A$ に対して操作する.

$A_N \neq x_q$ ならば, $A_I=x_q$ として, $A_I, A_{I+1}$ を入れ替える.
$A_N = x_q$ ならば, $A_N, A_{N-1}$ を入れ替える.

最終的な $A$ を求めよ.

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq x_q \leq N$

解法

数列 $A$ だけでなく, 次のようにして, $B$ を定める: $A_{B_i}=i$ . この $B$ は要素 $i$ がどこにあるかを記録する変数である.

この列 $B$ を利用することにより, 要素 $x_q$ の場所を $O(1)$ 時間で特定できる. これから必要な要素を交換して処理することで各操作を $O(1)$ で処理できる.

よって, 全体で $O(N+Q)$ で処理できる.