正題

題目鏈接:https://www.luogu.com.cn/problem/P5459

---

題目大意

$n$個數，求有多少個區間和在$[L,R]$范圍內。

---

解題思路

顯然我們做了前綴和之后，枚舉右端點就只需要找到有多少個左端點滿足在$[x?R,x?L]$這個范圍內就好了。

將前綴和離散化之后用樹狀數組維護即可（也不知道這為啥是紫題）

時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) #define ll long long using namespace std; const ll N=1e5+10; ll n,L,R,cnt,t[N],a[N],b[N],ans; void Change(ll x,ll val){while(x<=cnt){t[x]+=val;x+=lowbit(x);}return; } ll Ask(ll x){ll ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans; } int main() {scanf("%lld%lld%lld",&n,&L,&R);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);b[++cnt]=(a[i]+=a[i-1]);}b[++cnt]=0;sort(b+1,b+1+cnt);cnt=unique(b+1,b+1+cnt)-b-1;Change(lower_bound(b+1,b+1+cnt,0)-b,1);for(ll i=1;i<=n;i++){ll l=lower_bound(b+1,b+1+cnt,a[i]-R)-b;//x-z<=R z>=x-Rll r=upper_bound(b+1,b+1+cnt,a[i]-L)-b-1;//x-z>=L z<=x-La[i]=lower_bound(b+1,b+1+cnt,a[i])-b;ans+=Ask(r)-Ask(l-1);Change(a[i],1);}printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的P5459-[BJOI2016]回转寿司【树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。