（线段树）P5459 [BJOI2016]回转寿司_洛谷 p5459

P5459 [BJOI2016]回转寿司

添加链接描述https://www.luogu.com.cn/problem/P5459
思路：题目意思就是求出有多少个区间和在L~R范围内，这符合线段树的区间求和，另外，线段树的范围上的点变成了b[r]-b[l-1]可能的值。
（线段树法）先求出前i项的和b[i],然后对范围 进行如下操作，附加代码做法是第一种，第二种差不多一样

因为b[i]的值最多也就是N的最大范围个，所以我们的线段树结点最多不会爆int，所以要动态分配，下面的ct就是计算这个的个数，

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=1e10+10;
typedef struct Node{
    int lson,rson;
    ll sum;
}node;
ll b[100010];
node a[100000000];//这个容量要大点，否则Runtime Error
int root,ct;//root是线段树的根，ct是线段树的结点个数
ll L=-INF,R=INF;//这个地方之前是int，导致我找了三个小时的错误
//L\R就是线段树的最大边界。
void pushup(int u){//更新父节点的值
    a[u].sum=a[a[u].lson].sum+a[a[u].rson].sum;
}

void update(int &u,ll l,ll r,ll x){//在这道题 ，就是插入可能的值，x就是插入的地方
    if(!u) u=++ct;
    if(l==r){
        a[u].sum+=1;
        return;
    }
    ll mid=l+r>>1;
    if(x<=mid) update(a[u].lson,l,mid,x);
    if(x>mid) update(a[u].rson,mid+1,r,x);
    pushup(u);
}
ll query(int u,ll l,ll r,ll x,ll y){//查询在x~y中有多少个点
    if(!u) return 0;
    if(x<=l&&y>=r) return a[u].sum;
    ll mid=l+r >>1;
    ll res=0;
    if(x<=mid) res+=query(a[u].lson,l,mid,x,y);
    if(y>mid) res+=query(a[u].rson,mid+1,r,x,y);
    return res;
}
int main(){
    ll low,high;
    int n;
    scanf("%d%lld%lld",&n,&low,&high);
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
        b[i]+= b[i-1];//前i项之和
    }
    root=++ct;

    update(root,L,R,0);//这里先插入0，是为了可以检测到b[i]是否满足，即一直吃到i;
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=query(root,L,R,b[i]-high,b[i]-low);/先查询
        update(root,L,R,b[i]);//后更新
    }
    printf("%lld\n",ans);
    return 0;
}
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