問題
https://atcoder.jp/contests/arc033/tasks/arc033_3
提出
https://atcoder.jp/contests/arc033/submissions/3828872
Segment Treeについて参考にしたサイト
http://www.creativ.xyz/arc033c-406
Segment Treeを使おうと思ったきっかけ
https://www.slideshare.net/iwiwi/ss-3578491
考察
- 平方分割より10倍難しかった
- 値を左右から絞り込んでいく
- Ｘ番目の数字は、A[1]からA[n]までの和を見てXを上回った瞬間の位置に探している値がある
- それを見つけるために、left, rightを定義してcenterの位置で和を見て絞り込んでいく
- なるほどーと思った
クラス化
- AC後、次回用にSegment Treeをクラス化した
- 記述量などは変化無し
- グローバル関数の書く順序を気にしなくていいのは利点
2020/10/30 multiset
- multisetの内部ではソートされてるのでは？ということで、
- multiset解法→TLE
- イテレータを移動させるadvanceにO(移動量)かかってそう
- TLE https://atcoder.jp/contests/arc033/submissions/17724705
2020/10/30 BIT解法
- 値域が収まるのでBIT可能
- X個目は二分探索
- AC https://atcoder.jp/contests/arc033/submissions/17724752
