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

平方分割 Square Root Decomposition 区間に対するクエリに対して高速に処理できる ここが詳しい 区間でのクエリであるが、ソートして平方分割して、各バケットでクエリに入る要素だけ抜き出す平方分割もある こういう問題 1.添字と共に昇順ソート 2.バケット毎に添え字ソート 3.各クエリについて全ての…