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

hamayanhamayan's blog

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

平方分割

  • Square Root Decomposition
  • 区間に対するクエリに対して高速に処理できる
  • ここが詳しい
  • 区間でのクエリであるが、ソートして平方分割して、各バケットでクエリに入る要素だけ抜き出す平方分割もある
    • こういう問題
    • 1.添字と共に昇順ソート 2.バケット毎に添え字ソート 3.各クエリについて全てのバケットのans[L][R]を取得してマージ
  • クエリの平方分割
    • Q個のクエリを分けて解く手法 資料