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)
Comments