1 条题解
-
1
#include <bits/stdc++.h> using namespace std; #define int long long const int inf = 1e10+1; const int maxn = 3e5+10; #define mid (l+r>>1) int n,root,a[maxn],pre[maxn],l,r; int ls[maxn<<5],rs[maxn<<5],sum[maxn<<5],id; void update(int &rt,int l,int r,int val) { if( !rt ) rt = ++id; if( l==r ){ sum[rt]++; return; } if( val<=mid ) update( ls[rt],l,mid,val); else update(rs[rt],mid+1,r,val); sum[rt] = sum[ls[rt]]+sum[rs[rt]]; } int ask(int &rt,int l,int r,int L,int R) { if( !rt ) rt = ++id; if( l>=L&&r<=R ) return sum[rt]; int ans = 0; if( L<=mid ) ans += ask(ls[rt],l,mid,L,R); if( R>mid ) ans += ask(rs[rt],mid+1,r,L,R); return ans; } signed main() { cin >> n >> l >> r; for(int i=1;i<=n;i++) { cin >> a[i]; pre[i] = pre[i-1]+a[i]; } update(root,-inf,inf,0); int ans = 0; for(int i=1;i<=n;i++) { ans += ask( root,-inf,inf,pre[i]-r,pre[i]-l ); update(root,-inf,inf,pre[i] ); } cout << ans; }
- 1
信息
- ID
- 2278
- 时间
- 1000ms
- 内存
- 250MiB
- 难度
- 9
- 标签
- 递交数
- 12
- 已通过
- 7
- 上传者