AtCoder Regular Contest 075：E - Meaningful Mean
問題
解法
a_l, a_(l + 1), ... , a_r の平均が K 以上であるには (a_l - K) + (a_(l + 1) - K) + ... + (a_r - K) が 0 以上であればよいので，a_i から K を引いた値で考える．また，a の累積和 a_imos を考えると，a_l ~ a_r が条件を満たすには a_imos_(l - 1) より大きい a_imos_k の個数だけ a_l を左端とする部分列が作れることが分かる．よって，この問題は「各 a_imos_i について，その値以上となる a_imos_k の k (k >= l) の個数を求め，その個数の和」を求める問題になる．
ここで，k >= l という条件が厄介で，素直に a_imos をソートして二分探索するだけでは正しい答えが求まらない（k < l となるような k も数えてしまうから）．現在考えている i に対して有効な a_imos はどれかを判定出来ればこの問題は解決できる．各 a_imos の値が有効である個数を b_(a_imos) とする．i を 1 から N に動かせば有効な a_imos の数は減っていくので，最初に a_imos_0 以外の全ての a_imos について b = 1 としておく．a_imos に重複がある場合は，重複する個数だけ b は増える．区間の左端を i としたとき，条件を満たす区間の取り方は a_imos をソートしたものを別の配列に持って置き，二分探索をすることでその候補が求まる．候補の区間のうち有効であるものの個数はその区間の中の b の和になる．また，区間の左端を i から i + 1 にするとき，a_imos_i が有効である個数が -1 されるので b_(a_imos_i) から 1 を引く． これは BIT と用いれば b に対する各操作が O(logN) で可能．全体で O(NlogN) となる．
解答
