对于序列{a},求出一段连续子序列[l,r],使得L≤∑ai≤R.
考虑枚举r从1~n,对于每个r找出有多少个l符合
可以先预处理前缀和数组s[],那么∑ai=s[r]-s[l-1];
L≤∑ai≤R→→→s[r]-R≤s[l-1]<=s[r]-L;
累加即可
#include<iostream>
#define re(a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=5e5+10;
const ll inf=1e10;//1e5*1e5
int n,m;
ll res,s[N];//s[]维护前缀和,可能会爆int
int u,cnt;//根节点编号,计数器
struct sgt{
int l,r;
int sum;//个数
#define ls (tr[u].l)
#define rs (tr[u].r)
#define lson ls,l,mid
#define rson rs,mid+1,r
#define check x<=l&&y>=r
}tr[N*40];
void up(int u){tr[u].sum=tr[ls].sum+tr[rs].sum;}
void upd(int &u,ll l,ll r,ll x){
if(!u)u=++cnt;//不存在该节点,则开辟一个
if(l==r){
++tr[u].sum;
return;
}
ll mid=l+r>>1;//注意将mid也开成ll
if(x<=mid)upd(lson,x);
else upd(rson,x);
up(u);
}
int ask(int u,ll l,ll r,ll x,ll y){
if(!u)return 0;
if(check)return tr[u].sum;
ll mid=l+r>>1;//注意将mid也开成ll
int res=0;
if(x<=mid)res+=ask(lson,x,y);
if(y>mid)res+=ask(rson,x,y);
return res;
}
int main(){
int L,R;
cin>>n>>L>>R;
re(1,n)scanf("%lld",s+i),s[i]+=s[i-1];
upd(u,-inf,inf,0);//将0插入线段树中,一个也不吃的情况
re(1,n){//边插入边查询
res+=ask(u,-inf,inf,s[i]-R,s[i]-L);
upd(u,-inf,inf,s[i]);
}
printf("%lld\n",res);
}