自动搬运

查看原文

来自洛谷，原作者为

	pure__Elysia **

搬运于2025-08-24 22:33:48，当前版本为作者最后更新于2022-10-17 16:00:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目链接

通过记录

前言

  个人认为这个方法比上面几位都要拉一点，但是很好想，也很好懂。因为我比较拉，为了求清晰一点，所以不管是题解还是代码都写的比较长，望 dalao 见谅。

题目描述

  给你一个长度为 $n$ 的正整数列，请你求出那些平均数大于等于给定值 $p$ 的连续子序列个数。

算法思路

  该题一看好像很简单，再想想好像有点难，但仔细一想也不难。

  首先很容易想到一个常用的事情，我们把每个数都减去 $p$ ，那么那些负数都相当于“拉低平均分”的，正数就是“拉高平均分”的。

  此时，我们记录一个前缀和，比如 $sum[i]$ 表示从 $1$ 到 $i$ 的和。如果是负数，那就是从 $1$ 开始，这一段平均数低了，否则就是符合条件的。

  那么问题来了，怎么处理那些不是以 $1$ 开头的那些连续子序列呢？我们意识到，如果前面有一个前缀和，到后面某一个前缀和，相对的上升了（本体也可以相对不变），就说明这俩中间夹的那些数是正的（也可以是 $0$），也就是说是“平均分合格”的。这就是一种合法的子序列。

  那么我们怎么去统计这些“相对上升”呢？很明显，这就是求顺序对的个数。

if(你知道顺序对怎么求)
	goto 细节处理
if(你不清楚顺序对是什么，该怎么求)
	goto 求顺序对

求顺序对

  顺序对，就是说一个一个列表中两个数满足 $a[i]>a[j]$ 且 $i<j$ 。那么这两个数就是一组“顺序对”。本体因为可以等于 $p$，故两个数可以相等。也许不应该叫顺序对而叫非逆序对吧。

  顺序对主要有归并排序和树状数组两个求法，我蒟蒻，只写得来树状数组，这里讲一下下：

  首先开一个值域树状数组。由于本题原数组值域在 $-1e9$ 与 $1e9$ 间，但至多 $1e6$ 个数，所以需要进行离散化。

  按照顺序，在离散化后数组一个数加入前，检测现在的树状数组内小于（本题可以等于）这个值的数有多少个（简单的树状数组区间查询）。那么顺序对的数量就加上这个“个数”。

  因为这些数都是你进来前进来的，而且又比你小，所以有几个数，你就多带来了几个顺序对。

  查询后，你便可以将这个数加进树状数组（简单的树状数组单点修改）。然后就可以开始下一个数的操作了

  这就是求顺序对，简单吧。

细节处理

  如果你刚才就去打了码，会发现过不了样例。问题是出在哪里呢？是这样的。我们求的都是“顺序对”，但是没有去考虑人家一来就是正的，不需要降这种情况。那我们其实也很简单，就是在原序列的第 $0$ 位加上一个 $0$ ，这样相当于加了一个为 $0$ 的初始状态，可以把那些以来就是正的那些数处理进去了。

代码实现

#pragma GCC optimize(2)//防抄又加速，岂不美哉
#include<bits/stdc++.h>
using namespace std;

#define int long long//记前缀和很有可能就炸了，所以要防祖宗
#define ri register int//卡常小习惯

int a[1000050];//原数列&-p后的数列
struct cma{
	int w,id;
}sum[1000050];//前缀和（处理前）

int lsh[1000050],tim;//离散化后的前缀和

int s[1000050];//树状数组

int n,p,ans;

inline int rd()//快读宝，一款真正智能的语音音箱
{
	int a=0,f=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) a=(a<<1)+(a<<3)+c-'0';
	return a*f;
}

bool cmp(cma a,cma b)//离散化前肯定要排序啊
{
	if(a.w==b.w) return a.id<b.id;
	else return a.w<b.w;
}

inline void ls()//进行离散化
{
	int tot=sum[0].w-1;//因为多开了一个0进去，所以从0开始
	for(ri i=0;i<=n;i++)
	{
		if(sum[i].w!=tot) tot=sum[i].w,tim++;
		lsh[sum[i].id]=tim;
	}
	return ;
}

inline int lowbit(int x)
{
	return x&(-x);
}

inline int ask(int x)//简单区间查询
{
	int res=0;
	while(x>=1)
	{
		res+=s[x];
		x-=lowbit(x);
	}
	return res;
}

inline void addwhole(int x)//简单单点修改
{
	while(x<=tim)
	{
		s[x]++;
		x+=lowbit(x);
	}
}

signed main()
{
	n=rd();
	
	sum[0].id=0,sum[0].w=0;
	for(ri i=1;i<=n;i++)
		a[i]=rd(),sum[i].w=sum[i-1].w+a[i],sum[i].id=i;
		
	p=rd();
	
	for(ri i=1;i<=n;i++)
		sum[i].w-=p*i;//全部减去p
		
	sort(sum,sum+n+1,cmp);//离散化前的排序
	
	ls();//离散化
	
	for(ri i=0;i<=n;i++)
	{
		ans+=ask(lsh[i]);//先统计
		addwhole(lsh[i]);//再加入
	}
	
	printf("%lld\n",ans);
	
	return 0;
	
}