AtCoder Regular Contest 075 E - Meaningful Mean
問題: https://atcoder.jp/contests/arc075/tasks/arc075_c
公式解説は座標圧縮 + Binary Indexed Tree(BIT)だけど、Randomized Binary Search Tree(RBST)で殴ると座標圧縮しなくていいので実装が楽。(ただし定数倍遅い気がする)
signed main() { ll n, k; cin >> n >> k; vector<ll> s(n+1); rep(i, n) { ll a; cin >> a; s[i+1] = s[i] + a-k; } RBST<ll> st; ll ans = 0; for(int i=n-1; i>=0; i--) { st.insert(s[i+1]); int pos = st.lowerBound(s[i]); ans += n-i-pos; } cout << ans << endl; }