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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| #include <bits/stdc++.h> #define int long long #define MAXN 100005 #define MAXM 1e12 using namespace std; 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<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } namespace SegmentTree{ struct node{ int l,r; int val; }tree[40*MAXN<<2]; #define lc tree[i].l #define rc tree[i].r inline void pushup(int i){ tree[i].val=tree[lc].val+tree[rc].val; } int tot; void Update(int &i,int l,int r,int index){ if (!i) i=++tot; if (l==r) { tree[i].val++; return ; } int mid=(l+r)>>1; if (index<=mid) Update(tree[i].l,l,mid,index); else Update(tree[i].r,mid+1,r,index); pushup(i); } int Query(int &i,int l,int r,int L,int R){ if (!i) i=++tot; if (L<=l&&r<=R){ return tree[i].val; } int mid=(l+r)>>1,ans=0; if (L<=mid) ans+=Query(lc,l,mid,L,R); if (mid<R) ans+=Query(rc,mid+1,r,L,R); return ans; } } using namespace SegmentTree; int a[MAXN],sum[MAXN]; #undef int int main(){ #define int long long int n=read(),L=read(),R=read(); for (register int i=1;i<=n;++i){ int x=read(); sum[i]=sum[i-1]+x; } int ans=0,root=0; for (register int i=0;i<=n;++i){ ans+=Query(root,-MAXM,MAXM,sum[i]-R,sum[i]-L); Update(root,-MAXM,MAXM,sum[i]); } printf("%lld\n",ans); }
|