この記事で紹介しているアルゴリズムが役に立つケースは少ないと思われます。あくまで「そういうことも理論上できる」くらいの内容で読んでいただけると幸いです。
自己紹介
はじめまして、@jiyujin816です。普段は競プロをしています(一応AtCoder水です)。Mo's Algorithmについて考察していたときに（個人的に）面白いことに気づいたので、既出かもしれませんが今回初めて記事を書いてみました。駄文ですがよろしくお願いします。
概要
長さ$N$の列に対して、区間に対するクエリがある程度の条件を満たしているなら、一回の区間の伸縮にかかる計算量を$f(N)$として$O(N^{3/2}f(N))$ほどの前処理で、オンラインで各クエリに$O(\sqrt{N}f(N))$で答えられる。
既出な気も列の平方分割のような気もしますが、私が調べた範囲では日本語の記事は見つからなかったし、列の平方分割とも少し違う気がしたのでMarkdownの練習も兼ねて書いてみました（記事があったら教えてくれると嬉しいです）。そもそもMo's Algorithmではない気がしますがそこは気にしないでくれると助かります。また、本記事では区間は基本的に閉区間を使い、列Aのi番目からj番目までを$A[i,j]$で表します。
普通のMo's Algorithm
以下の記事で紹介されているように、長さ$N$の列に対するオフラインクエリに対して、クエリ数を$Q$として前処理$O(Q\log Q)$（本質ではない）でクエリに$O((N+Q)\sqrt{N}f(N))$(工夫すると$O(N\sqrt{Q}f(N))$)で解けます。
Mo's Algorithmが使えるのは基本的には、以下の条件を満たしているときです。
- クエリの途中で列が変化しない
- $[l,r]$に対するクエリを解いたあと高速に、$[l-1,r],[l,r+1],[l+1,r],[l,r-1]$に対するクエリの結果が求められる
- クエリがオフラインで与えられる
以上の条件を満たしていればMo's Algorithmが使えます。逆に言えば、クエリがオンラインで与えられる場合は、Mo's Algorithmは使えないのです。
オンラインで解ける条件
ここからが本題です。以下の条件を満たしているときMo's Algorithmのようなことをして、オンラインで列の区間に関するクエリが解けます。
- クエリの途中で列が変化しない
- $[l,r]$のクエリを解いた後$[l,r+1],[l-1,r],[l+1,r],[l,r-1]$（工夫すればもう少し減らせる）についてのクエリが高速に計算できる
- 2.の計算をするために必要なデータが軽いor永続データ構造などに載せられる
「永続データ構造に載せられる」という場合は$\log N$倍ほど時間がかかるため、TLEになる可能性がとても高いです（大事なことなので2回言いました）
名前があるのかもしれませんが、とりあえずこれをオンラインMo's Algorithmみたいに呼びます。（本当はなんて名前なんですかね...）
オンラインMo's Algorithm(仮)
前処理パート
$B=\lfloor\sqrt{N}\rfloor,S=\lfloor\frac{N-1}{B}\rfloor$として、区間$[0,0],[0,B],[0,2B]...[0,BS][B,B]...[BS,BS]$をオフラインクエリだと思い、普通のMo's Algorithmを使って区間の伸縮に必要なデータを何らかの方法で保存します。
クエリ処理パート
与えられる各クエリ[l,r]に対して、区間$[\lfloor\frac{l}{B}\rfloor\times B,\lfloor\frac{r}{B}\rfloor\times B]$について保存したデータを使い、Mo's Algorithmのように計算していきます。
以上です。これでMo's Algorithm？でオンラインクエリができるようになりました。これをMo's Algorithmと言っていいのかはかなり疑問ですが...
オンラインMo's Algorithmの計算量
計算量を見積もってみます。まず、前処理パートです。
前処理パートでは$\frac{(S+1)(S+2)}{2}$個のクエリを普通のMo's Algorithm解いています。$S\fallingdotseq\sqrt{N}$なのでクエリの数は大体$O(N)$個になります。長さ$N$の列の$O(N)$個のクエリを解いているので計算量は$O((N+N)\sqrt{N}f(N))=O(N^{3/2}f(N))$くらいです。
そして、各クエリに対しては区間の伸縮は高々$2B-2$回しか行われないので1クエリあたり$O(\sqrt{N}f(N))$で解けます。
よって、全体での計算量は$O((N^{3/2}+Q\sqrt{N})f(N))$になります。
問題例
ABC423EをオンラインMo's Algorithmで解いてみます。もとの問題はオフラインでクエリが与えられるので普通のMo's Algorithmで解けますが、あえてオンラインMo's Algorithmを使います。
問題文の意訳
長さ$N$の数列$A$が与えられるから。各$L_i,R_i$について$A[L_i,R_i]$の全ての連続部分列の総和の総和を求めてね
普通のMo'sで解く
詳細は省略しますが、$\sum_{x=l}^{r}A[x],\sum_{x=l}^{r}(r-x+1)A[x],\sum_{x=l}^{r}(x-l+1)A[x]$と、$A[l,r]$の全ての連続部分列の総和の総和を保持しておけばMo's Algorithmが使えます。
提出コード(287ms)
オンラインMo's Algorithmで解く
区間の伸縮に必要な情報は上記の4つの数値だけなので、愚直に2次元配列で値を管理しておけば問題に正解できます。
提出コード(299ms)
問題例2
ABC293GもオンラインMo'sで解いていきたいと思います（解けませんでした）。
普通のMo's Algorithmで解く
区間$[l,r]$の処理をするときに区間内の各整数の個数を持った配列$cnt$と条件を満たす組の個数を持ちながら区間を伸縮させれば解けます。
提出コード(216ms)
オンラインMo's Algorithmで解く（願望）
とりあえず作れるペアの個数は愚直に2次元配列で管理して良さそうです。問題は$cnt$です。この配列は長さ$N$なので$O(N)$個の配列を持つと空間計算量が$O(N^2)$で破滅しています。だめじゃん。
部分永続配列
突然ですが、区間$[aB,bB]$と$[aB,(b+1)B]$ではどれだけ配列$cnt$に差が出るかを考えてみます。$[aB,bB]$での$cnt$に$B$個の数値を追加したものが$[aB,(b+1)B]$での$cnt$になります。このとき、$cnt$の変わる項の数は高々$B$個なので残りの$N-B$個はそのままです。そのため、変更された項のみを保存することを考えると、保存しないといけないものは$O(N^{3/2})$個くらいに減ります。これはほぼ部分永続配列なので、以下の記事を参考にすると
構築が$O(N^{3/2})$一点取得は$O(\log N)$でできるようになります。
ここまで来たらあとは普通に先ほどと同じようにオンラインMo's Algorithmをしてあげれば解けるのではないでしょうか？
ところがどっこいTLE
上の文を書いてるときはノリノリで「賢い方法考えたな～」とか思ってましたが、ちゃんと計算量を考えると$O(N^{3/2}+Q\sqrt{N}\log{N})$なのでだいたい$ (2\times10^5)^{3/2}+(2\times10^5)(\sqrt{2\times10^5}){\log(2\times10^5)} \fallingdotseq 1.66\times10^9回$くらいの処理が必要です。これではTLEしても仕方ないです。
一応SIMDや$_nC_3$の前計算、クエリを処理するときのベースのブロック調整、分割サイズの調整とかで多少マシになったのが以下のコードです。
提出コード(TLE9ケース)
（TLEになるコードをたくさん提出して申し訳ない...）
頑張れば通せるのかもしれませんが私は諦めました。暇な人はやってみてもいいかもしれません。
必要な条件の削減
すでにこのアルゴリズムの使いどころを見失いかけていますが、ここまで書いてしまったので最初に書こうと思ったことは書きます。
ここで言った通り、工夫すれば必要な条件を減らせます。snukeさんのブログに倣って$[l,r]$の結果から$[l-1,r],[l,r+1]$の結果を求めることを追加操作、$[l+1,r],[l,r-1]$の結果を求めることを削除操作と呼ぶことにします。オンラインMo's Algorithmでは、追加操作のみがあれば答えが求められます。
前処理パート
各$i(0\le i<S)$について、以下のように処理します。
- $[Bi,Bi]$の結果を求める
- $[Bi,B(i+1)],[Bi,B(i+2)]...$の結果を順に求めていく
これで前処理パートは追加操作のみで処理できました。
クエリ処理パート
1.$[L_i,R_i]$についてもし、$R_i-L_i\le B$なら愚直に計算します。もしそうでないなら、$L_i\le Bl$を満たす最小の$l$と$Br\le R_i$を満たす最大の$r$を求めます。
2. 区間$[Bl,Br]$から区間を伸長させていき、答えを求めます。
計算量は変わらず、$O((N^{3/2}+Q\sqrt{N})f(N))$です。
おわりに
思いついたときは「結構良くね？」と思ってましたが、実際に実装してみると思いのほか$\log N$倍の悪化がきつかったです。あまり記事にされてないのにはそれなりの理由があるのだと痛感しました。
あまり有効に使える場面が想像できませんが知ってたら役に立つことがあるかもしれません。
ここまで読んでいただきありがとうございます。
参考記事