AtCoder Regular Contest 075 E - Meaningful Mean
数列が与えられる。連続部分列の平均値が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やセグメント木に配列の値そのものをインデックスとして持つ、みたいなテクニックは以前見たことあったのだけど、思い出せなかった。