かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

yukicoder No.2002 Range Swap Query

競技プログラミング 解説 典型 yukicoder

問題はこちら

問題概要

長さ{N}の数列{P}と{K}個の操作があり，操作{i}は{P_{A_i}}と{P_{B_i}}を入れ替える．
以下の{Q}個のクエリを処理せよ．
操作{L_j,L_j+1,\cdots ,R_j}をこの順に行ったときの{P_{X_j}}を求めよ．

  • {2\leq N\leq 4×10^5}
  • {1\leq K\leq 2×10^5}
  • {1\leq Q\leq 2×10^5}
  • {1\leq A_i < B_i \leq N}
  • {1\leq L_j \leq L_j \leq K}
  • {1\leq X_j \leq N}

解説

このクエリはオフラインで処理できるのでMo's algorithmが使えないかを考える．

Mo's algorithmについては以下の記事を参照
kanpurin.hatenablog.com

{[l,r)}の答え(状態)から{[l±1,r),[l,r±1)}の答え(状態)が高速に計算できればMo's algorithmを適用することができる．

{[l±1,r)}を左側への追加/削除，{[l,r±1)}を右側への追加/削除と言うことにする．
操作{i}を左側に追加/削除する場合，{P_{a}=A_i,P_{b}=B_i}となるような{a,b}に対し，{P_{a},P_{b}}を入れ替える．
操作{i}を右側に追加/削除する場合，{P_{A_i},P_{B_i}}を入れ替える．

これらは全て{O(1)}でできるので全体で{O(N\sqrt{Q})}で解くことができる．

提出プログラム

https://yukicoder.me/submissions/776935

感想