回转寿司 – HYSBZ 4627 – 线段树

来源： 回转寿司 – 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;
}