はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるMo's Algorithm問題まとめ

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))でも間に合う
  • 派生が色々ある