来源: 回转寿司 – HYSBZ 4627 – Virtual Judge
数组s表示前缀和,那么题意就是要找有多少对符合条件的i,j (i < j)使得L<=s[j]-s[i]<=R,也就是s[j]-R<=s[i]<=s[j]-L,换句话说,就是求在s[j]-R到s[j]-L之间的前缀和的个数,我参考的题解用的类似权值线段树的做法,但只要想明白要求什么做法就不重要了。
代码
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; const ll inf=1e11; int sum[maxn*40],ls[maxn*40],rs[maxn*40]; int o,tot,n,L,R; void updata(int &o,ll l,ll r,ll v) { if(!o) o=++tot; ++sum[o]; if(l==r)return; ll mid=(l+r)>>1; if(v<=mid) { updata(ls[o],l,mid,v); } else updata(rs[o],mid+1,r,v); } ll query(int o,ll le,ll ri,ll l,ll r) { if(l<=le&&ri<=r) return sum[o]; ll mid=(le+ri)>>1,ans=0; if(l<=mid) ans+=query(ls[o],le,mid,l,r); if(r>mid) ans+=query(rs[o],mid+1,ri,l,r); return ans; } int main() { ios::sync_with_stdio(false); cin>>n>>L>>R; updata(o,-inf,inf,0);//初始化前缀和为0 ll num=0,ans=0,d; for(int i=1;i<=n;i++) { cin>>d; num+=d;//当前前缀和 ans+=query(o,-inf,inf,num-R,num-L);//查询区间内有多少个数 updata(o,-inf,inf,num);//更新个数 } cout<<ans<<endl; return 0; }