 /**//*
题意:给出n个数 问多少个区间,使得平均值>a n≤10^5
枚举左右指针可以知道多少个,但是O(n^2) TLE
枚举左右指针,找对数,不是跟逆序对很像?有O(nlogn)算法
设sum[i]=∑x[i]-a
若区间[i,j]平均值>a 则有 sum[j]-sum[i-1] = x[j]-a + x[j-1]-a + + x[i]-a>0 即sum[i]<sum[j]
所以问题转化为有多少对sum[i]<sum[j] ,i<j
由于可以是区间[1,j]满足条件,即sum[0]<sum[j] 所以加多一个sum[0]=0

*/
#include<cstdio>
#include<cstring>

const int MAXN = 100010;

long long sum[MAXN];
long long _sum[MAXN];

long long merge(int beg,int end)//find sum[i]<sum[j]
  {
long long ans = 0;
int mid=(beg+end)>>1;
int i=beg,j=mid+1,c=beg;
while(i<=mid&&j<=end)
 {
if(sum[i]>=sum[j])_sum[c++]=sum[i++];
else
 {
ans+=(mid-i+1);
_sum[c++]=sum[j++];
}
}
while(i<=mid)_sum[c++]=sum[i++];
while(j<=end)_sum[c++]=sum[j++];
while(beg<=end)sum[beg]=_sum[beg++];
return ans;
}
long long mergeSort(int beg,int end)
  {
if(beg>=end)return 0;
int mid=(beg+end)>>1;
long long ans = 0;
ans+=mergeSort(beg,mid);
ans+=mergeSort(mid+1,end);
ans+=merge(beg,end);
return ans;
}
int main()
  {
//freopen("in","r",stdin);
int T,N,A;
for(scanf("%d",&T);T--;)
 {
scanf("%d%d",&N,&A);
sum[0]=0;
for(int i=1,x;i<=N;i++)
 {
scanf("%d",&x);
x-=A;
sum[i]=sum[i-1]+x;
}
printf("%I64d\n",mergeSort(0,N));
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|