perogram

セグメント木 再訪 (AtCoder C - データ構造)

Quiz

https://atcoder.jp/contests/arc033/tasks/arc033_3

Submit

https://atcoder.jp/contests/arc033/submissions/5012167

解法

  • 「X番目の値」をlog(200000)くらいの高速で見つける必要がある
  • セグメント木を使う
  • 各値のカウントを持っていて、[0, 指定の値) までのカウントの和を返すように作る
  • それができれば二分探索を用いて「X番目の値が何か」が求められる

資料

感想

  • 4ヶ月前くらいにセグメント木は1度作っていたが、苦労して書いた印象
  • 今回はそれを少し改良して使っただけだが、理解のUPを感じる

今後の課題

  • 遅延評価セグメント木