LibreOJ L3735 「COCI 2015.11」 VUDU

https://loj.ac/p/3735

套路 \(\times 3\)。

对于求平均数，直接对每一个 \(a_i\gets a_i-P\)，和 \(\ge 0\) 的连续子序列就满足平均数 \(>P\)。

然后对其进行前缀和处理 \(s_i=\sum\limits_{j=1}^{i-1}a_j\)，则连续子序列的和就可以转为差分处理，只要 \(s_r-s_l\ge 0(l<r)\) 则说明满足条件。

然后能发现这玩意就是求 \(i < j, s_i\le s_j\) 的个数（注意有一个开头的 \(s_0=0\)），维护即可。

# include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
vector <long long> hsh;
int m;
int getsum (long long x) {
	return lower_bound (hsh .begin (), hsh .begin () + m, x) - hsh .begin ();
}
long long a [N + 10], t [(N + 10) << 1];
void add (int u) {
	for (int i = u; i <= (int) hsh .size (); i += i & -i) {
		++ t [i];
	}
	return ;
}
long long query (int u) {
	long long ans = 0;
	for (int i = u; i; i -= i & -i) {
		ans += t [i];
	}
	return ans;
}
int main () {
	int n;
	scanf ("%d", & n);
	for (int i = 1; i <= n; ++ i) {
		scanf ("%lld", & a [i]);
	}
	long long p;
	scanf ("%lld", & p);
	for (int i = 1; i <= n; ++ i) {
		a [i] += a [i - 1] - p;
		hsh .push_back (a [i]);
	}
	hsh .push_back (LONG_LONG_MIN);
	hsh .push_back (0);
	sort (hsh .begin (), hsh .end ());
	m = unique (hsh .begin (), hsh .end ()) - hsh .begin ();// 离散化
	long long ans = 0;
	add (getsum (0));// 记得先扔一个 0
	for (int i = 1; i <= n; ++ i) {
		ans += query (getsum (a [i]));
		add (getsum (a[i]));
	}
	printf ("%lld", ans);
	return 0;
}