以下の内容はhttps://kanpurin.hatenablog.com/entry/2022/07/09/035354より取得しました。

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

感想

以上の内容はhttps://kanpurin.hatenablog.com/entry/2022/07/09/035354より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14