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

hamayanhamayan's blog

競技プログラミングにおける平方分割問題まとめ

平方分割

  • Square Root Decomposition
  • 区間に対するクエリに対して高速に処理できる
  • ここが詳しい
  • 平方分割を理解しておくと、Mo's algorithmを理解しやすい

メモ

ある区間においてある数値よりも大きい要素の数、小さい要素の数を求めるのに使用。難しめ。
分割区間のidxを持っておき、ソートしておくと、lower_boundなどで1区間に対し対数時間で個数が得られる。