Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ARC075 C - Meaningful Mean】平均がK以上

理解したのでまとめておきます。

E - Meaningful Mean

問題

数列Aが与えられる。N(N+1)/2個ある区間のうち、平均がK以上のものはいくつあるか?

制約: Ai=109, N=105

方針

平均Kと聞くと脊髄反射的に引きたくなります。つまり数列をDi=Ai-Kとして、この区間和が正になるものはいくつあるか?という問題とわかります。

区間和は、区間[l,r)として、[0,r)から[0,l)を引いたものです。[0,i)は累積和で計算出来ます。これをBiとします。

すると、Biについて、Bj<=Bi (j<=i)のものはいくつあるかという話になります。

これは転倒数の考え方(の逆)と同じですが、計算のためにBITを使おうとすると、Aiの値が大きいことから、MLEします。

そこで、Biを座圧してから問題を解きます。

BITを使った転倒数の求め方を復習しておきます。

f:id:akiradeveloper529:20191008182635j:plain