Skip to content →

Mo’s algorithm で解ける問題

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)

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA