疑问为什么线段树4n还会RE

zzs2731 @ 2024-09-19 22:10:04

by UnyieldingTrilobite @ 2024-09-19 22:23:02

@zzs2731 这样分享代码会存在有人（我）看不到，方便直接贴一下吗？

by Love_Natsu @ 2024-09-20 13:48:59

@UnyieldingTrilobite 直接贴就被删贴了

别问我怎么知道的

by zzs2731 @ 2024-09-20 20:56:41

@UnyieldingTrilobite

#include<bits/stdc++.h>
using namespace std;
long long qread(){
    long long ret=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        ret=ret*10+ch-'0';
        ch=getchar();
    }
    return ret*f;
}
int n,q;
long long a[1000050];
struct node{
    long long v,x,l,r,tag;
    bool f;
}tri[4000050];
void build(int p,long long l,long long r){
    tri[p].l=l;
    tri[p].r=r;
    if(l==r){
        tri[p].v=a[l];
        return;
    }
    long long mid=l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tri[p].v=max(tri[p*2].v,tri[p*2+1].v);
}
void f1(int p,long long x){
    tri[p].v=x;
    tri[p].x=x;
    tri[p].tag=0;
    tri[p].f=1;
}
void f2(int p,long long x){
    tri[p].v+=x;
    tri[p].tag+=x;
}
void pushdown1(int p){
    tri[p].f=0;
    f1(p*2,tri[p].x);
    f1(p*2+1,tri[p].x);
}
void pushdown2(int p){
    f2(p*2,tri[p].tag);
    f2(p*2+1,tri[p].tag);
    tri[p].tag=0;
}
void update(int op,int p,long long l,long long r,long long k){
    if(op==1&&tri[p].l>=l&&tri[p].r<=r){
        f1(p,k);
        pushdown1(p);
        return; 
    }
    if(op==2&&tri[p].l>=l&&tri[p].r<=r){
        f2(p,k);
        return;
    }
    if(tri[p].f==1)pushdown1(p);
    pushdown2(p);
    long long mid=tri[p].l+tri[p].r>>1;
    if(l<=mid)update(op,p<<1,l,r,k);
    if(r>mid)update(op,p<<1|1,l,r,k);
    tri[p].v=max(tri[p*2].v,tri[p*2+1].v);
//  cout<<tri[p].l<<' '<<tri[p].r<<' '<<tri[p].v<<endl; 
}
long long query(int p,long long l,long long r){
    if(tri[p].l>=l&&tri[p].r<=r)return tri[p].v;
    if(tri[p].f==1)pushdown1(p);
    pushdown2(p);
    long long mid=tri[p].l+tri[p].r>>1,ret=-1e18;
    if(l<=mid)ret=max(ret,query(p*2,l,r));
    if(r>mid)ret=max(ret,query(p*2+1,l,r));
//  cout<<tri[p].l<<' '<<tri[p].r<<' '<<tri[p].v<<endl;
    return ret;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)a[i]=qread();
    build(1,1,n);
    long long l,r,x;
    for(int op,i=1;i<=q;i++){
        op=qread();
        if(op==1){
            l=qread();
            r=qread();
            x=qread();
            update(1,1,l,r,x);
        }
        if(op==2){
            l=qread();
            r=qread();
            x=qread();
            update(2,1,l,r,x);
        }
        if(op==3){
            l=qread();
            r=qread();
            printf("%lld\n",query(1,l,r));
        }
    }
    return 0;
} 

RE代码

#include<bits/stdc++.h>
using namespace std;
long long qread(){
    long long ret=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        ret=ret*10+ch-'0';
        ch=getchar();
    }
    return ret*f;
}
int n,q;
long long a[1000050];
struct node{
    long long v,x,l,r,tag;
    bool f;
}tri[5000050];
void build(int p,long long l,long long r){
    tri[p].l=l;
    tri[p].r=r;
    if(l==r){
        tri[p].v=a[l];
        return;
    }
    long long mid=l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tri[p].v=max(tri[p*2].v,tri[p*2+1].v);
}
void f1(int p,long long x){
    tri[p].v=x;
    tri[p].x=x;
    tri[p].tag=0;
    tri[p].f=1;
}
void f2(int p,long long x){
    tri[p].v+=x;
    tri[p].tag+=x;
}
void pushdown1(int p){
    tri[p].f=0;
    f1(p*2,tri[p].x);
    f1(p*2+1,tri[p].x);
}
void pushdown2(int p){
    f2(p*2,tri[p].tag);
    f2(p*2+1,tri[p].tag);
    tri[p].tag=0;
}
void update(int op,int p,long long l,long long r,long long k){
    if(op==1&&tri[p].l>=l&&tri[p].r<=r){
        f1(p,k);
        pushdown1(p);
        return; 
    }
    if(op==2&&tri[p].l>=l&&tri[p].r<=r){
        f2(p,k);
        return;
    }
    if(tri[p].f==1)pushdown1(p);
    pushdown2(p);
    long long mid=tri[p].l+tri[p].r>>1;
    if(l<=mid)update(op,p<<1,l,r,k);
    if(r>mid)update(op,p<<1|1,l,r,k);
    tri[p].v=max(tri[p*2].v,tri[p*2+1].v);
//  cout<<tri[p].l<<' '<<tri[p].r<<' '<<tri[p].v<<endl; 
}
long long query(int p,long long l,long long r){
    if(tri[p].l>=l&&tri[p].r<=r)return tri[p].v;
    if(tri[p].f==1)pushdown1(p);
    pushdown2(p);
    long long mid=tri[p].l+tri[p].r>>1,ret=-1e18;
    if(l<=mid)ret=max(ret,query(p*2,l,r));
    if(r>mid)ret=max(ret,query(p*2+1,l,r));
//  cout<<tri[p].l<<' '<<tri[p].r<<' '<<tri[p].v<<endl;
    return ret;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)a[i]=qread();
    build(1,1,n);
    long long l,r,x;
    for(int op,i=1;i<=q;i++){
        op=qread();
        if(op==1){
            l=qread();
            r=qread();
            x=qread();
            update(1,1,l,r,x);
        }
        if(op==2){
            l=qread();
            r=qread();
            x=qread();
            update(2,1,l,r,x);
        }
        if(op==3){
            l=qread();
            r=qread();
            printf("%lld\n",query(1,l,r));
        }
    }
    return 0;
} 

AC代码