这题是洛谷P2717的弱化版，也是前缀和优化题

假设有一个满足条件的子序列在$[a_l,a_r]$间，显然，一共有$r-l+1$个数字，由于这些数的平均数大于等于$k$即：

$a_l+a_{l+1}+.......+a_{r-1}+a_r≥(r-l+1)*k$

稍稍亿一变形可得

$a_l+a_{l+1}+.......+a_{r-1}+a_r-(r-l+1)*k≥0$

$(a_l-k)+(a_{l+1}-k)+.......+(a_{r-1}-k)+(a_r-k)≥0$

所以我们可以在输入时对每个$a_i$减$k$，在查找时直接判断是否大于0即可

再看前缀和优化部分，假设我们挑选了这样一个子序列：

$a_1, a_2, ... , a_l, a_{l+1}, ... , a_{mid} , ... , a_{r-1}, a_r, ...$

显然$[a_l,a_{mid}]$部分的和相当于$a_l$的后缀和，而$[a_{mid+1},a_r]$部分的和相当于从$a_{mid+1}$开始，到$a_r$的前缀和

注意：从$a_{mid+1}$开始！！！！！

因为序列是分为两部分的，如果从$a_1$开始，必然会把$[a_1, a_{mid}]$的部分多余算

但你以为这就完了么？

实际上手还会超时的！！！

这就意味着我们得继续减复杂度

毕竟是前缀和，我们只需要看区间和满足不满足要求，调换顺序不影响。所以可以通过排序来减少多余的区间计算

我们可以将$[a_1, a_{mid}]$的部分从大到小排，剩下的部分从小到大排，再用双指针扫一遍，结束！

上代码：

#include<bits/stdc++.h>
using namespace std;
long long a[100001],s[100001];
bool cmp(long long x,long long y){
    return x>y;
}
int main(){
    long long n,k,ans=0,j;
    cin>>n>>k;
    j=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]-=k;
    }
    int mid=(n+1)/2;
    for(int i=1;i<=mid;i++) s[i]=s[i+1]+a[i]; //后缀和
    for(int i=mid+1;i<=n;i++) s[i]=s[i-1]+a[i]; //前缀和
    sort(s+1,s+mid+1,cmp);  //既然排序不影响，那就梭哈一下给双指针做贡献
    sort(s+mid+1,s+n+1);
    for(int i=1;i<=mid;i++){
        while(j>mid&&s[i]+s[j]>=0){
            j--;          //双指针扫描
        }
        ans+=(n-j);
     }
     cout<<ans;
}