P2880 10分 求助,为什么我写的线段树对于有些询问输出0?

回复帖子

@ztx666  2020-08-01 17:40 回复

rt,把数据下载下来看了一下,发现对于有些询问输出0

样例能过

大佬们能帮我审一下代码吗?希望是些睿智错误

题目

评测结果

#include <bits/stdc++.h>
using namespace std;
#define MAXN 50005
#define INF 1000000000000LL
typedef long long ll;
ll n,q,a[MAXN],tree_max[MAXN*4],tree_min[MAXN*4];
void build(ll rt,ll l,ll r){
    if(l==r){
        tree_max[rt]=tree_min[rt]=a[l];
    }else{
        ll mid=(l+r)/2;
        build(rt*2,l,mid);
        build(rt*2+1,mid+1,r);
        tree_max[rt]=max(tree_max[rt*2],tree_max[rt*2+1]);
        tree_min[rt]=min(tree_min[rt*2],tree_min[rt*2+1]);
    }
}
ll query_max(ll rt,ll l,ll r,ll L,ll R){
    if(L<=l&&R>=r){
        return tree_max[rt];
    }else{
        ll mid=(l+r)/2,ret=0;
        if(L<=mid){
            ret=max(ret,query_max(rt*2,l,mid,L,R));
        }else if(R>mid){
            ret=max(ret,query_max(rt*2+1,mid+1,r,L,R));
        }
        return ret;
    }
}
ll query_min(ll rt,ll l,ll r,ll L,ll R){
    if(L<=l&&R>=r){
        return tree_min[rt];
    }else{
        ll mid=(l+r)/2,ret=INF;
        if(L<=mid){
            ret=min(ret,query_min(rt*2,l,mid,L,R));
        }else if(R>mid){
            ret=min(ret,query_min(rt*2+1,mid+1,r,L,R));
        }
        return ret;
    }
}
int main(){
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    build(1,1,n);
    for(ll i=1;i<=q;i++){
        ll l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",query_max(1,1,n,l,r)-query_min(1,1,n,l,r));
    }
    return 0;
}

数据#2前50行输出结果:

0
0
0
637497
0
0
0
0
854711
0
94741
0
0
0
246772
0
0
0
0
0
936515
897022
984031
0
0
0
0
823421
847236
0
859753
0
0
0
0
0
0
0
0
946582
0
891211
0
0
157160
0
0
333444
0
0

我太弱了qwq

@ASTROBOY 2020-08-01 18:01 回复 举报

查询的地方逻辑有问题,第二个else应该去掉,L<mid存在不代表r>mid不存在啊。
5 1
1 2 3 4 5
2 4

@ztx666  2020-08-01 18:08 回复 举报

@ASTROBOY 谢谢大佬,已经过了qwq

还真是睿智错误,我太弱了

看来我还是得再背一下敲几遍线段树233

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。