4. 小埋的解密游戏
题目ID：15880必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
小埋最近在玩一个解密游戏，这个游戏会提供 nn 个数。
我们需要求出：在这 nn 个数里面，有多少个连续的数的平均数大于某个给定的数 MM 。
这个数量可能会很大，所以我们要输出这个数对 10000000071000000007 的取模结果。
请你帮小埋求出结果。
输入格式
输入有两行。第一行为两个数 nn 和 MM 。第二行为 nn 个数。
输出格式
输出的数占一行，即问题的解对 10000000071000000007 取模的结果。
样例
Input 1
4 3 1 5 4 2
Output 1
5
Input 2
4 4 5 2 7 3
Output 2
6
样例解释
对于测试样例1，对于这4个数，有 5 组数字符合要求：{1,5,4}，{5}，{5,4}，{5,4,2}，{4}。
数据范围
1<=n<=2∗1051<=n<=2∗105
1<M<=3∗1031<M<=3∗103
所有的数均为正整数且不大于5000
思路：
先把原数组的所有数 - m
然后如果一个数对平均值有贡献，那么 - m之后一定是正数，否则是非正数。
然后写一个前缀和，相当于求
j>=i
sum[j]-sum[i-1]>0
我一寻思，这不就是顺序对吗？
然后我就把前缀和数组颠倒了，然后写了个逆序对别问我为什么
然后WA0pts了QAQ
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m;
int A[200005];
int a[200005];
int c[200005];
int fw[200005];
long long sortt(int l,int r){
if(l==r){
return 0;
}
int mid=(l+r)/2;
long long ans=0;
ans+=sortt(l,mid);
ans+=sortt(mid+1,r);
int p=l,q=mid+1;
for(int i=l;i<=r;i++){
if(q>r||p<=mid&&a[p]<a[q]){
c[i]=a[p++];
ans+=q-(mid+1);
}
else{
c[i]=a[q++];
}
}
for(int i=l;i<=r;i++){
a[i]=c[i];
}
return ans;
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&A[i]);
A[i]-=m;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+A[i];
}
for(int i=1;i<=n;i++){
fw[i]=a[n-i+1];
}
for(int i=1;i<=n;i++){
a[i]=fw[i];
}
cout<<sortt(1,n);
return 0;
}
/*
颠倒空格
*/