Mo’s algorithm は、

• \(f(l, r)\) から \(f(l\pm1, r)\) が高速に求まる。
• \(f(l, r)\) から \(f(l, r\pm1)\) が高速に求まる。

という条件の下で、区間 \([l, r]\) について、\(f(l, r)\) を求めよというクエリがオフラインで高速に処理できる。

処理できるクエリの例

• \(a_{l},\ldots,a_{r}\)の最頻値
• \(a_{l},\ldots,a_{r}\)の k 番目に小さい値
• \(a_{l},\ldots,a_{r}\)で同じ数をペアにしたとき、何個のペアができるか。(ABC242G)
• \(a_{l},\ldots,a_{r}\)には何種類の数があるか。(ABC174F)
• \(a_{l},\ldots,a_{r}\)の総積の約数の個数(dwacon2017e)
• \(N\) 個の区間が与えられる。区間\([L_i, R_i]\) に含まれる区間は何個か
• \(a_{l},\ldots,a_{r}\)の和がKになる部分列の個数（CF442F）
• \(a_{l},\ldots,a_{r}\)に含まれる、要素が相異なる連続部分列の個数（HackerRank 101 Hack 52 C）