ARC075 E. Meaningful Mean - phyllo’s algorithm note

問題

長さNの整数列aに対して、空でない連続する部分列の算術平均がK以上であるものの個数を答えよ。

制限

2 <= N <= 2*10^5
1 <= K <= 10^9, Kは整数
1 <= a[i] <= 10^9

解説

https://atcoder.jp/img/arc075/editorial.pdf
AtCoder Regular Contest 075 / Beginner Contest 063 解説放送 - YouTube

愚直に計算するとO(N^3)や、すぐ思いつく方法ではO(N^2)で、TLE。

ある範囲[l,r)について、条件は「(Σ_{i=l}^{r-1} a[i]) / (r-l) >= K」と書ける。
これを変形すると、

<=> Σ_{i=l}^{r-1} a[i] >= (r-l)*K
<=> Σ_{i=0}^{r-1} a[i] - Σ_{i=0}^{l-1} a[i] >= (r-l)*K
<=> Σ_{i=0}^{r-1} a[i] - r*K >= Σ_{i=0}^{l-1} a[i] -l*K

<=> b[r] >= b[l]
   ただし、b[x] = Σ_{i=0}^{x-1} a[i] - x*K

となる。
この変換によって、配列bの要素の大小関係の問題(転置数)になる。

この問題は、値を座圧っぽく変換して、BITを使って0～i-1まででb[i]以下の個数を求めればO(NlogN)で計算できる。

反省

数式で書き出せるものは書いて、変形してみる