题意

求一段长为$n$的序列，连续的平均值大于$m$的方案数是多少？

解析

把每个数减$m$求前缀和，要求一段的和大于$0$,所以转化为一个位置的$sum$大于前面的$sum$,即求顺序对

#include <bits/stdc++.h>
using namespace std;
const int maxn=500002;
int n,m;
int a[maxn],bak[maxn];
long long ans;
void Sort(int L,int R)
{
    if(L==R)
        return;
    int mid=(L+R)>>1;
    Sort(L,mid);
    Sort(mid+1,R);
    int i=L,j=mid+1,k=L;
    while(i<=mid&&j<=R)
    {
        if(a[i]<a[j])
        {
        	ans+=i-L+1;
            bak[k++]=a[i++];
        }else
            bak[k++]=a[j++];
    }
	while(i<=mid)
        bak[k++]=a[i++];
    while(j<=R)
        bak[k++]=a[j++];
    for(int p=L;p<=R;p++)
    {
        a[p]=bak[p];
        bak[p]=0;
        //printf("%d ",a[p]);
    }
    //printf("\n");
    return;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[i]=a[i-1]+x-m;
	}
	for(int i=n+1;i>=1;i--)
		a[i]=a[i-1];
	Sort(1,n+1);
	printf("%lld",ans);
}