ABC174 F - Range Set Query - かんプリンの学習記録

Mo's algorithmを用いた方法を説明します．

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の数列に関して「 ${l_i}$ 番目から ${r_i}$ 番目までに含まれる数の種類を求めよ」という ${Q}$ 個のクエリに答えよ．

${1\leq N,Q \leq 5×10^5}$

解説

Range Set Queryという名前とか数列の区間に対するクエリとかからSegmentTreeを使いそうだが，区間のマージ操作に時間がかかってしまい無理．

以下の条件を満たすときMo's algorithmというものが使える．

更新クエリがない
${[l,r)}$ の答え(状態)から ${[l±1,r),[l,r±1)}$ の答え(状態)が高速に計算できる．
オフラインで処理できる．

※「オフラインで処理できる」とは ${[l,r)}$ の答えを求めるクエリに答える順番は関係ない、という感じです．答えを求めるクエリの間に更新クエリがあるとこれができなくなります．(2022/01/08 追記)

今回の問題はこれを満たしているのでMo's algorithmが使える．

Mo's algorithmの考え方について説明する．
${[l,r)}$ のクエリがある場合に ${(l,r)}$ に点をプロットしたような二次元平面上を考える．

入力例 ${2}$ での例

このように考えることにより， ${[l,r)}$ から ${[l±1,r),[l,r±1)}$ への変化が二次元平面上で上下左右に ${1}$ 移動することとみなせる．

この移動を繰り返し，全点をできるだけ少ない移動で訪れる巡回セールスマン問題のようなものになる．

ここで， ${L}$ (横軸)を ${K}$ 分割し(二次元平面を縦に切る)，分割されたグループごとに順に訪れることにすると， ${R}$ (縦軸)方向の移動回数は ${1}$ つのグループにつき ${O(N)}$ ，グループ内で ${L}$ 方向の移動回数は点ごとに ${O(N/K)}$ (1つのグループの ${L}$ 方向の長さが ${O(N/K)}$ )であるから，上下左右に ${1}$ 移動する操作が ${O(T)}$ でできるとすると全体の計算量は ${O(TN(Q/K+K))}$ となる．これを最小にするような ${K}$ は ${\sqrt{Q}}$ なので ${\sqrt{Q}}$ 分割することにより ${O(TN\sqrt{Q})}$ で解くことができる．

今回の問題は ${O(T)=O(1)}$ なので ${O(N\sqrt{Q})}$ で解くことができる．これでもC++などの高速な言語なら間に合う．移動の仕方として，すべてのグループで ${R}$ の昇順に訪れるのではなくて，昇順に訪れるグループと降順に訪れるグループを交互に(蛇行するように)すると速くなる．