解密游戏
题目ID：15880 (满分100分)
时间限制: 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
蒟蒻看出：
a[l]+a[l+1]+a[l+2]+…+a[r]
------------------------------------ >m
r-l+1
则
(a[l]-m)+(a[l+1]-m)+(a[l+2]-m)+...+(a[r]-m)>0
于是：
/*
在前缀和里找顺序对
*/
#include<iostream>
#define mod 1000000007
#define int long long
using namespace std;
int n,m,a[200005],s[200005],ans,tmp[200005];
void merge_sort(int a[],int l,int r){
if(l>=r)return ;
int mid=(l+r)/2;
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r){
if(a[i]<=a[j]){
tmp[k++]=a[i++];
ans=(ans+r-j+1)%mod;
}else{
tmp[k++]=a[j++];
}
}
while(i<=mid)tmp[k++]=a[i++];
while(j<=r)tmp[k++]=a[j++];
for(int i=l;i<=r;i++){
a[i]=tmp[i];
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]-=m;
s[i]=s[i-1]+a[i];
}
merge_sort(s,0,n);
cout<<ans;
return 0;
}
可是样例居然不过！！！
怎么回事？
是 归并排序错了 还是 统计错了？
帮我调一下吧求求了！