NOMURA プログラミングコンテスト2022 (AtCoder Beginner Contest 253) G - Swap Many Times (600)
愚直に操作をすると$ \mathcal{O}(N^2)になってしまう
実際に操作を試してみると
$ (1,x) の操作が終わると配列は$ [N,1,2,...] の様になる
$ (2,x) の操作が終わると配列は$ [N,N-1,1,2,...] の様になる
よって以下の手順でも配列を求められる
最初のあるx全てを覆わないようなが開始するまでの結果を考える
$ x-1までの操作結果は上の方法で求められる
最初から処理をした場合とは異なりここが$ 1,2,...,Nになるので値の対応表を作っておく
覆われている部分は上の方法で求められる
最後の残りの処理を実際に行う
実際に処理を行うところについて$ Lが高々2つなので$ \mathcal{O}(N)で求められる