Mo's Algorithm
- pekempeyさんの最強解説 ei1333さんの最強解説
- pekempeyさんの記事に乗っていることですが「要素が更新されない」「クエリの先読みが可能」「区間 [L,R] の結果から [L-1, R], [L+1, R], [L, R-1], [L, R+1] の結果が容易に得られる」という条件が大切
- 計算量はO( (N+Q)√N) で、追加削除はO(1)かO(logN)が求められることが多く（O(logN)は大体計算量オーバー）、答えを求める部分はO(sqrt(N))でも間に合う
- 派生が色々ある
- Mo's Algorithmの上位互換があり、永続データ構造と組み合わせることで解ける問題が増える
- この上位互換では範囲を増やすのは自由だけど、減らすのは難しい(Rollbackでしか出来ない)場合は上位互換を使う
- 時空間Mo's Algorithm
- 木上でのMo's Algorithm
- Mo's Algorithmの上位互換があり、永続データ構造と組み合わせることで解ける問題が増える
問題
- 通常のMo's Algorithm
- HR Unique Art
- HackerRank Week of Code 31 Nominating Group Leaders 平方分割+Mo's Algorithm
- 第3回 ドワンゴからの挑戦状 本選 B. ニワンゴくんの約数 Mo's Algorithm+それ以外の難しい高速化
- CF429 Destiny
- CF442 Ann and Books
- CF204 Jeff and Removing Periods 解説
- HR Car Show 解説
- HE Powerful Pair in Tree
- 時空間Mo's Algorithm
