AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の44問目である「Shift and Swapping（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【044 – Shift and Swapping（★3）】
考察
Q < 10**5という制約から、各クエリに対して、計算量はO(1)である必要があります。
操作の種類Tが1もしくは3の場合、その処理はO(1)で行うことができますので、これらについては問題ありません。
しかし、操作の種類が2（T==2）の場合、配列全体を直接ずらすという直観的な操作は、要素数に応じてO(N)の計算量を必要とします。このような計算量は許容範囲を超えてしまいます。
そこで、配列の並び順に着目します。例えば、配列が
6 17 2 4 17 19 1 7
であったとき、T==2の操作が来ると、
7 6 17 2 4 17 19 1
となります。ここで重要なのは、配列の先頭位置は変化しますが、配列自体の並び順は変化しないという点です。
このことから、T==2の操作回数を、配列の先頭位置がずれた回数として考えることができます。
つまり、先頭がずれた回数（cnt）を保持し、T==2の操作が来たときには、cntを1減らします。そして、各要素の位置xを、(x+cnt)%Nとして計算します。これにより、先頭の位置が変化しても、その位置を正しく表現することができます。
コード
N,Q = map(int, input().split())
A = list(map(int, input().split()))
#リストAの先頭の位置を表す変数cntを0に初期化
cnt = 0
for q in range(Q):
T,x,y = map(int, input().split())
x -= 1 #0-indexにするため-1
y -= 1
if T == 1:
A[(x+cnt)%N],A[(y+cnt)%N] = A[(y+cnt)%N],A[(x+cnt)%N]
#リストの先頭の位置がcntだけずれているため、入れ替えるインデックスは(x+cnt)%Nと(y+cnt)%N
elif T == 2:
cnt -= 1#リストの先頭の位置を1つ後ろにずらします。具体的には、変数cntから1を引きます。
#ここで、Pythonのリストのインデックスは負の数を指定することでリストの末尾からアクセスできるため、cntが負の数になるとリストの先頭が最後尾に移動
elif T == 3:
print(A[(x+cnt)%N])
#リストの先頭の位置がcntだけずれているため、実際のインデックスは(x+cnt)%N
コメント