AtCoder Regular Contest 052 B : 円錐

arc052.contest.atcoder.jp

解法

典型的なRMQ問題(足すやつもMinimumっていうんでしょうか・・・)

円錐を高さ1ごとにぶつ切りした体積を配列に持たせて、
それをSegmentTreeに入れてあげて更新作業をすれば、
あとはクエリーに答えていくだけ。

計算量も事前の計算にO(max(B)(N + log max(B))、クエリーにO(Q log max(B))なので
問題なさそう。

SegmentTreeを使ってもよかったが、BITをライブラリ化していたので
そちらを使う。

Submission #950479 - AtCoder Regular Contest 052 | AtCoder



TODO: SegmentTreeの実装