平方分割で解いた問題をSegment Treeで解き直した arc033_3

問題

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倍難しかった
  • 値を左右から絞り込んでいく
    • X番目の数字は、A[1]からA[n]までの和を見てXを上回った瞬間の位置に探している値がある
    • それを見つけるために、left, rightを定義してcenterの位置で和を見て絞り込んでいく
    • なるほどーと思った

クラス化

  • AC後、次回用にSegment Treeをクラス化した
  • 記述量などは変化無し
  • グローバル関数の書く順序を気にしなくていいのは利点