AtCoder Regular Contest 075 E: Meaningful Mean

http://arc075.contest.atcoder.jp/tasks/arc075_c

条件を数式に落とし込むと
∑(i=0→r)Ai - rK という値について考えればいいことがわかる。数式を使うと独立性に気付ける問題だった。
あとは適当に座圧してBITで数え上げればよい。

int n;

//BIT 1-origin

ll bit[MAX_N];

ll sum(int i) {
	ll s = 0;
	while(i > 0) {
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add(int i, ll x) {
	while(i <= n) {
		bit[i] += x;
		i += i & -i;
	}
}

int N;
ll K;
ll B[MAX_N];
vector<ll> vec;

int fd(ll a) {
	return lower_bound(all(vec), a) - vec.begin();
}

void solve() {
	cin >> N >> K;
	rep(i, 1, N + 1) {
		cin >> B[i];
		B[i] += B[i - 1];
	}
	rep(i, 1, N + 1) {
		B[i] -= K * i;
		vec.push_back(B[i]);
	}
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	n = vec.size();
	ll res = 0;
	rep(i, 0, N + 1) {
		res += sum(fd(B[i]) + 1);
		add(fd(B[i]) + 1, 1);
	}
	cout << res << "\n";
}

数式をtexで書けるようになりたい。