/*
给定一个数组，要求和小于t的段落总数
求前缀和
dp[i]表示以第i个数为结尾的小于t的段落总数，sum[i]-sum[l]<t;
sum[i]-t<sum[l],所以只要找到满足条件的sum[l]数量即可
将sum排序，每次找到sum[i]-t的排名，大于它的就是l的数量
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
ll tmp[maxn],n,a[maxn],t,sum[maxn],ans;
ll bits[maxn];
void add(
int x,
int val){
for(
int i=x;i<=n+
1;i+=i&-
i)
bits[i]++
;
}
ll query(int x){
ll ans =
0;
for(
int i=x;i>
0;i-=i&-
i)
ans +=
bits[i];
return ans;
}
int main(){
cin>>n>>
t;
memset(bits,0,
sizeof bits);
for(
int i=
1;i<=n;i++)cin>>
a[i];
for(
int i=
1;i<=n;i++)sum[i]=sum[i-
1]+
a[i];
for(
int i=
1;i<=n;i++)tmp[i]=
sum[i];
sort(tmp,tmp+
1+n);
//带着0排序
//add(0,1);
for(
int i=
1;i<=n;i++
){
int pos=lower_bound(tmp,tmp+n+
1,sum[i-
1])-tmp+
1;
add(pos,1);
pos=upper_bound(tmp,tmp+n+
1,sum[i]-t)-
tmp;
ans+=i-
query(pos);
}
printf("%lld\n",ans);
}
转载于:https://www.cnblogs.com/zsben991126/p/10372424.html
