競技プログラミング用 知識集積所
ABC436F - Starry Landscape Photo
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
明るさがk番目である星が写真に写る最も暗いものである撮り方を考える。
明るさが1～k-1番目である星が左にL個、右にR個あったとすると、そのような撮り方は(L+1)(R+1)個ある。
したがって、このLとRがすぐに求められれば、あとはkごとに(L+1)(R+1)を求めて合計するだけ。
明るさが1～k-1番目である星が左にL個、右にR個あったとすると、そのような撮り方は(L+1)(R+1)個ある。
したがって、このLとRがすぐに求められれば、あとはkごとに(L+1)(R+1)を求めて合計するだけ。
Rは実はk-1-Lですぐ求められるので実質Lだけ求められればよく、これはFenwick木※上に左から順にカウンティングしていくことで簡単に実現できる。
解答例
注意点
解答にはlong long型を用いる。
答えがおおよそO(N^2)になるので、int型では入りきらない。
