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

平方分割

• Square Root Decomposition
• 区間に対するクエリに対して高速に処理できる
• ここが詳しい
• 区間でのクエリであるが、ソートして平方分割して、各バケットでクエリに入る要素だけ抜き出す平方分割もある
  • こういう問題
  • 1.添字と共に昇順ソート 2.バケット毎に添え字ソート 3.各クエリについて全てのバケットのans[L][R]を取得してマージ
  • 出現頻度を扱う場合は平方分割が多いイメージ
• クエリの平方分割
  • Q個のクエリを分けて解く手法 資料
• 取得クエリだけで更新クエリが無い場合はバケットの間の処理は事前計算することで、処理をより軽くすることができる場合がある この解説

問題

• 平方分割
  • AOJ Range Query - Range Sum Query (RSQ)
  • AOJ Range Query - Range Minimum Query (RMQ)
  • AOJ Range Query - Range Add Query (RAQ)
  • AOJ Range Query - Range Sum Query (RSQ)
  • Codeforces #404 Div2 E. Anton and Permutation
  • CF91 Lucky Array 解説1 解説2 解説3
  • CC Hill Jumping
  • AOJ RMQ 2 解説
  • CC Chef and Isomorphic Array （ハッシュの知識も必要）
  • CF260 Serega and Fun 解説
  • CF542 Isolation
• クエリの範囲で分けない平方分割
  • CSA Closest Numbers
• クエリの平方分割
  • CF119 Xenia and Tree 解説1 解説2
  • AOJ Graph Construction 解説1 解説2
  • AOJ Tree 解説
  • JOI 回転寿司 解説1 解説2
  • CSA55 Black White Tree
  • CC Killing Monsters （＋ゼータ変換）
• 二次元平方分割
  • AOJ School of Killifish 解説
  • CodeChef Rectangle Query ←違うかも