読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

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

平方分割

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

問題

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