AtCoder Regular Contest 075 E - Meaningful Mean

問題はこちら

問題概要

長さ{ \displaystyle N}の数列{ \displaystyle a_0, a_1, \cdots, a_{N-1}}が与えられたとき、平均が{ \displaystyle K}以上となる部分列の個数を求めよ。

公式解説概要

pdfはこちら

{ \displaystyle b_j = \sum_{i=0}^{j-1} a_i − jK (0 \leq j \leq N)}とおいて、{ \displaystyle b_r > b_l (r > l)}となる{ \displaystyle r, l}の組を求める。{ \displaystyle b_i}を{ \displaystyle 0, 1, \cdots, N}の範囲の{ \displaystyle c_i}に変更し、{ \displaystyle 0, 1, \cdots, N}の値の出現回数をBITを用いて保持する。これにより、{ \displaystyle i = 0, 1, \cdots, N}のそれぞれに対し、{ \displaystyle c_0, c_1, \cdots, c_{i-1}} に{ \displaystyle c_i}以下の値が何回出現したかをそれぞれ{ \displaystyle O(\log(N))}時間で計算することができる。

分からなかったこと

BITを使うと、なぜ各値の出現回数を保持できるのだろう、、、と思ったけど、indexに各値を、valueに{ \displaystyle 1}を代入して引数として関数に渡せばいいだけだった。各値以下の出現回数からBITを想起するにはまだまだ修行が必要そう。