E - Meaningful Mean AtCoder Regular Contest 075

E: Meaningful Mean - AtCoder Regular Contest 075 | AtCoder
問題概略
長さNの数列Aで、算術平均がK以上になる区間はいくつあるか。

制約
N 10 ^5
a,K < = 10^9

解法
ある区間の算術平均がK異常かを判定するには、sum - K * len が0以上かを見ればいい。
これはaの各要素からKを引いておくことで、合計が0以上の区間を数える問題に出来る。
後は、aの累積和を取り、その転倒数を数えることで答えがわかる。

類題
D - Median of Medians

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        int K = ni();
        A = nia(N);
        for (int i = 0; i < N; i++) {
            A[i] -= K;
        }
        long[] rui = rui(A);
        compress(rui);
        BIT b = new BIT(N * 2);
        long res = 0;
        for (int i = 0; i < N+1; i++) {
            res += b.sum(0, (int) rui[i]+1);
            b.add((int) rui[i], 1);
        }
        System.out.println(res);
    }

    static class BIT {
        long[] dat;
        int N;

        BIT(int n) {
            N = n;
            dat = new long[n + 1];
        }

        // 0 index
        void add(int i, int v) {
            i++;
            while (i < dat.length) {
                dat[i] += v;
                i = i + (i & -i);
            }
        }

        //開区間
        long _sum(int i) {
            if (i <= 0) return 0;
            return dat[i] + _sum(i - (i & -i));
        }

        //半開区間
        long sum(int l, int r) {
            return _sum(r) - _sum(l);
        }
    }