アルゴリズム忘備録

競技プログラミングとかデータ分析とか

AtCoder Regular Contest 075 E - Meaningful Mean

arc075.contest.atcoder.jp

 

数列が与えられる。連続部分列の平均値がK以上であるような部分列は何通りあるか?

 

まずすぐ分かることはすべての要素からKを引くと、部分列の和が0以上になるような組み合わせをカウントすればよい。これはO(N^2)であれば、累積和を使ってカウントできる。

 

ただし計算量の問題があるので、累積和をsum[i]などと書くと、sum[0]~sum[i - 1]までにsum[i]以下の物が何通りあるか、というのをO(logN)以下で計算する必要がある。これは結構よく見るテクで、値そのものをIndexに持つセグメント木 or BITを使うと良い。ただし、値をIndexに持つので、値自体はO(10^6)以下でなければならないため座標圧縮を用いる。

 

すると、例えばBITを用いて、BIT.sum(sum[i])の和を取りつつ、sum[i]番目のBITにどんどん1を足していく、というループを回すと答えになる。O(N logN)。

 

このBITやセグメント木に配列の値そのものをインデックスとして持つ、みたいなテクニックは以前見たことあったのだけど、思い出せなかった。