线段树50分求助,已经调了一天了

P1253 扶苏的问题

QCurium @ 2023-07-19 11:17:09

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int Q=1e6+5;
const ll inf=1e9;
ll n,q,as[N];
struct node{
    ll l,r;
    ll tag;
    ll mx,bg;
}a[(1<<21)+5];
void push_up(ll aa){
    a[aa].mx=max(a[aa*2].mx,a[aa*2+1].mx);
}
void push_down(ll aa){
    if(a[aa].bg!=-inf){
        a[aa*2].bg=a[aa].bg;
        a[aa*2+1].bg=a[aa].bg;
        a[aa*2].mx=a[aa].bg;
        a[aa*2+1].mx=a[aa].bg;
        a[aa].bg=-inf;
        a[aa*2].tag=0;
        a[aa*2+1].tag=0;
    }
    if(a[aa].tag!=0){
        if(a[aa*2].bg!=-inf)
            a[aa*2].bg+=a[aa].tag;
        else
            a[aa*2].tag+=a[aa].tag;
        if(a[aa*2+1].bg!=-inf)
            a[aa*2+1].bg+=a[aa].tag;
        else
            a[aa*2+1].tag+=a[aa].tag;
        a[aa*2].mx+=a[aa].tag;
        a[aa*2+1].mx+=a[aa].tag;
        a[aa].tag=0;
    }
}
void built(ll aa,ll l,ll r){
    a[aa].l=l;
    a[aa].r=r;
    a[aa].bg=-inf;
    a[aa].tag=0;
    if(l==r){
        a[aa].mx=as[l];
        return ;
    }
    ll mid=(l+r)>>1;
    built(aa*2,l,mid);
    built(aa*2+1,mid+1,r);
    push_up(aa);
}
ll search(ll aa,ll l,ll r){
    if(a[aa].l>=l&&a[aa].r<=r)
        return a[aa].mx;
    push_down(aa);
    ll mxx=-inf;
    ll mid=(a[aa].l+a[aa].r)>>1;
    if(mid>=l)
        mxx=max(mxx,search(aa*2,l,r));
    if(mid<r)
        mxx=max(mxx,search(aa*2+1,l,r));
    return mxx;
}
void bj(ll aa,ll l,ll r,ll z){
    if(a[aa].l>=l&&a[aa].r<=r){
        a[aa].mx=z;
        a[aa].bg=z;
        a[aa].tag=0;
        return ;
    }
    push_down(aa);
    ll mid=(a[aa].l+a[aa].r)>>1;
    if(l<=mid)
        bj(aa*2,l,r,z);
    if(r>mid)
        bj(aa*2+1,l,r,z);
    push_up(aa);
    return ;
}
void add(ll aa,ll l,ll r,ll k){
    if(a[aa].r<=r&&a[aa].l>=l){
        if(a[aa].bg!=-inf)
            a[aa].bg+=k;
        else
            a[aa].tag+=k;
        a[aa].mx+=k;
        return ;
    }
    push_down(aa);
    ll mid=(a[aa].l+a[aa].r)>>1;
    if(mid>=l)
        add(aa*2,l,r,k);
    if(mid<r)
        add(aa*2+1,l,r,k);
    push_up(aa);
    return ;
}
int main(){
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&as[i]);
    built(1,1,n);
    for(ll i=1;i<=q;i++){
        ll lx;
        scanf("%lld",&lx);
        if(lx==1){
            ll xx,yy,kk;
            scanf("%lld%lld%lld",&xx,&yy,&kk);
            bj(1,xx,yy,kk);
            continue;
        }
        if(lx==2){
            ll xx,yy,kk;
            scanf("%lld%lld%lld",&xx,&yy,&kk);
            add(1,xx,yy,kk);
            continue;
        }
        if(lx==3){
            ll xx,yy;
            scanf("%lld%lld",&xx,&yy);
            printf("%lld\n",search(1,xx,yy));
            continue;
        }
    }
    return 0;
}

各位奆佬,蒟蒻已经调一天了,救救孩子吧


by jr_zch @ 2023-07-19 11:43:13

我看了一下,你的函数没有什么问题


by jr_zch @ 2023-07-19 11:44:48

你的 inf 是不是太小了点,都开 long long 了,inf1 \times 10^9,我开成了 1 \times 10^{18} 就可以通过我下载下来的第 6 个测试点了。


by jr_zch @ 2023-07-19 11:49:44

我用你的代码开 1 \times 10^{18} 已经通过了,别的地方一点问题没有。。


by ganglao @ 2023-07-19 11:53:07

inf定得太小了,要定成long long 的最大负数。


by QCurium @ 2023-07-19 12:47:47

@jr_zch @ganglao 十分感谢两位大佬对蒟蒻的帮助


by QCurium @ 2023-07-19 12:53:28

我现在过了,十分感谢


by WhitD @ 2023-07-19 14:07:31

const long long INF=0x7FFFFFFFFFFFFFFF

万岁


|