[COCI2015-2016#2] VUDU

[COCI2015-2016#2] VUDU

题意

求一个序列中有多少个子段平均数大于 \(P\)。

思路

区间和相关的问题可以考虑前缀和。

对于原序列前缀和序列 \(a\)，询问等价于求数对 \((l,r)(l\le r)\) 的个数，满足：

移项整理得：

令 \(b_i=a_i-Pi\)，就是求 \(b\) 中的顺序对个数，树状数组求即可。

坑点：实现时要往树状数组中先插入 \(0\)，所以离散化时也要离散化 \(0\)，树状数组值域开到 \(n+1\)。

代码

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e6 + 5;

int n, tot;
ll ans, a[N], b[N], P;

struct BIT {
	ll t[N];
	void add(int x, ll y) {
		for (int i = x; i <= n + 1; i += i & (-i)) {
			t[i] += y;
		}
	}
	ll query(int x) {
		ll res = 0;
		for (int i = x; i; i -= i & (-i)) {
			res += t[i];
		}
		return res;
	}
} T;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	cin >> P;
	for (int i = 1; i <= n; i ++) {
		a[i] -= 1ll * i * P;
		b[++ tot] = a[i];
	}
	b[++ tot] = 0;
	sort(b + 1, b + tot + 1);
	tot = unique(b + 1, b + tot + 1) - b - 1;
	for (int i = 0; i <= n; i ++) {
		a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
	}
	T.add(a[0], 1);
	for (int i = 1; i <= n; i ++) {
		ans += T.query(a[i]);
		T.add(a[i], 1);
	}
	cout << ans << "\n";
	return 0;
}