暴力怎么搞，维护前缀和 $s[i]$ ，对于每一个 $s[i]$，枚举所有 $jin[0,i-1]$，看看 $s[i]-s[j]$ 是否属于 $[L,R]$
如果属于就加入答案
$s[i]-s[j]in[L,R]$ 等价于 $s[i]-s[j] geqslant L , s[i]-s[j] leqslant R$
即 $s[i]-L geqslant s[j] , s[i]-R leqslant s[j]$
发现对于每一个 $i$ 其实就是问区间 $[0,i-1]$ 中权值在 $[s[i]-L,s[i]-R]$ 之间的 $s[j]$ 的数量
直接权值树状数组，发现值域太大，所以要离散化
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7; int n,L,R; int t[N]; ll ans,a[N],s[N];//注意long long inline void add(int x) { while(x<=n+1) t[x]++,x+=x&-x; } inline int ask(int x) { int res=0; while(x) res+=t[x],x-=x&-x; return res; } int main() { n=read(),L=read(),R=read(); for(int i=1;i<=n;i++) a[i]=s[i]=s[i-1]+read(); sort(a+1,a+n+2); for(int i=0;i<=n;i++)//注意i=0 { int tr=lower_bound(a+1,a+n+2,s[i]-L+1)-a-1;//这个等价于upper_bound(a+1,a+n+2,s[i]-L)-a-1; int tl=lower_bound(a+1,a+n+2,s[i]-R)-a; ans+=ask(tr)-ask(tl-1); add(lower_bound(a+1,a+n+2,s[i])-a); } printf("%lld ",ans); return 0; } //si-sj>=L si-L>=sj sj<=si-L //si-sj<=R si-R<=sj sj>=si-R