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で書けるようになりたい。