Quiz
https://atcoder.jp/contests/arc033/tasks/arc033_3
Submit
https://atcoder.jp/contests/arc033/submissions/5012167
解法
- 「X番目の値」をlog(200000)くらいの高速で見つける必要がある
- セグメント木を使う
- 各値のカウントを持っていて、[0, 指定の値) までのカウントの和を返すように作る
- それができれば二分探索を用いて「X番目の値が何か」が求められる
資料
- iwiさんのスライド
- tsutajさんのBlog
- この2つをこの順番で読めば十分
感想
- 4ヶ月前くらいにセグメント木は1度作っていたが、苦労して書いた印象
- 今回はそれを少し改良して使っただけだが、理解のUPを感じる
今後の課題
- 遅延評価セグメント木
