给定一个序列，求有多少个子区间满足区间和大于等于 (L) 且小于等于 (R) 。
像这样的区间信息可以拆分成前缀和的，也就是具有区间可减性的信息，我们可以直接求一遍前缀和。
然后我们发现题目就变成了求点对数量了，而且这里很明显就是一个二维偏序问题，求 (i<j) 且 (Lleq a_j-a_i leq R) 的点对 ((i,j)) 的个数。
可以使用 CDQ 分治，也可以直接上动态开点线段树，也可以离线离散化然后树状数组。
没怎么懂 CDQ分治 的写法，这里采用动态开点线段树。
代码：
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
const int N=1e5+5;
const ll INF=1e10;
int n,L,R,a[N],top,root;
ll pre[N];
int sum[N*220],ls[N*220],rs[N*220],cur;
void Modify(int &x,ll l,ll r,ll pos,int v){
if(!x) x=++cur;
ll mid=l+r>>1;sum[x]+=v;
if(l==r) return ;
if(pos<=mid) Modify(ls[x],l,mid,pos,v);
else Modify(rs[x],mid+1,r,pos,v);
return ;
}
int Query(int x,ll l,ll r,ll ql,ll qr){
if(ql>qr||!x) return 0;
if(ql<=l&&r<=qr) return sum[x];
ll mid=l+r>>1,res=0;
if(ql<=mid) res+=Query(ls[x],l,mid,ql,qr);
if(qr>mid) res+=Query(rs[x],mid+1,r,ql,qr);
return res;
}
ll Ans;
int main(){
read(n),read(L),read(R);
Modify(root,-INF,INF,0,1);
for(int i=1;i<=n;i++){
read(a[i]);
pre[i]=pre[i-1]+a[i];
Ans+=Query(root,-INF,INF,pre[i]-R,pre[i]-L);
Modify(root,-INF,INF,pre[i],1);
}
write(Ans);
return 0;
}