自动搬运

查看原文

来自洛谷，原作者为

	ghj1222 阿绫最可爱啦

搬运于2025-08-24 21:40:47，当前版本为作者最后更新于2019-02-09 17:14:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非常简单的cdq分治

先把所有数-=k，转化为平均数>=0的区间数量

也就是区间和>=0的区间数量

对于区间[l, r]内部所有区间的贡献，令区间中点为mid，先计算[l, mid]和[mid + 1, r]的所有贡献，然后再计算[l, r]内所有跨过区间中点mid的区间贡献就行

跨过中点的区间一定是$i\in[l,mid]$的一段[i, mid]和$j\in[mid + 1, r]$的一段[mid + 1, j]组成，我们前面求后缀和后面求前缀和把所有上述区间和搞出来，然后分别排序双指针扫一遍就可以统计答案了

有前缀和转化为逆序对的做法，实质其实一样，都是cdq分治

#include <cstdio>
#include <algorithm>
using namespace std;

int n, k, a[100010];
int tmp[100010];

long long cdq(int l, int r)
{
	if (l == r) return a[l] >= 0;
	int mid = (l + r) / 2;
	long long ans = cdq(l, mid) + cdq(mid + 1, r);
	tmp[mid] = a[mid];
	tmp[mid + 1] = a[mid + 1];
	for (int i = mid - 1; i >= l; i--)
		tmp[i] = tmp[i + 1] + a[i];
	for (int i = mid + 2; i <= r; i++)
		tmp[i] = tmp[i - 1] + a[i];
	sort(tmp + l, tmp + mid + 1);
	sort(tmp + mid + 1, tmp + r + 1);
	for (int i = l, j = r; i <= mid; i++)
	{
		while (j > mid && tmp[i] + tmp[j] >= 0) j--;
		ans += r - j;
	}
	return ans;
}

int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] -= k;
	printf("%lld\n", cdq(1, n));
	return 0;
}