树状数组好题

思路

题目的要求就相当于存在一个sum[r]-sum[l-1]<t的关系,然后我门可以写成sum[r]-t<sum[l-1],所以我们可以先处理一个前缀和数组,然后类比求逆序对的方式,查找在他之前出现的sum[i]>sum[k]-t并且k>i的数量就好了,要注意的一点就是我们在0的位置有一个sum[0]=0不能忽略掉

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//By AcerMo
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) x&(-x)
#define lli long long int
using namespace std;
const int M=200500;
lli n,m;
lli b[M],a[M],s[M];
inline void read(lli &x)
{
x=0;int f=1;char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return (void)(x=f?x:-x);
}
inline void add(int p,int x)
{
for (int i=p;i<=n+1;i+=lowbit(i)) s[i]+=x;
return ;
}
inline lli sum(int p)
{
lli su=0;
for (int i=p;i;i-=lowbit(i)) su+=s[i];
return su;
}
signed main()
{
read(n);read(m);
for (int i=1;i<=n;i++)
read(a[i]),a[i]+=a[i-1],b[i]=a[i];
sort(b,b+n+1);lli ans=0;
for (int i=1;i<=n;i++)
{
add(lower_bound(b,b+n+1,a[i-1])-b+1,1);
ans+=(i-sum(lower_bound(b,b+n+1,a[i]-m+1)-b));
}
cout<<ans;
return 0;
}