2018-12-19 平方分割して管理する (arc033_3) 問題 atcoder.jp 平方分割を使っても解ける問題 平方分割とは 長さLのリストを sqrt(L) で分割する 参考 プログラミングコンテストでのデータ構造 from Takuya Akiba www.slideshare.net 提出 atcoder.jp vectorにpush_backする度にsort 遅そうだが、リストの長さは平均的に sqrt(200000) = 約500 なので間に合った テストデータに偏りがあったら引っかかるだろう🤔 追記 なぜ sqrt(N) が効くのか、式で見ると自明 https://trap.jp/post/152/