线段树20分求助，悬关，谢谢！

lcbridge @ 2023-05-07 16:47:21

#include <bits/stdc++.h>
#define int long long
#define MAXN 1000005
#define none -114514
using namespace std;
int n,q,a[MAXN];
struct SegmentTree{
    int l,r,len,maxx;
    int add,to;
}t[MAXN*4];
void pushup(int x){
    t[x].maxx=max(t[x*2].maxx,t[x*2+1].maxx);
}
void build(int x,int l,int r){
    t[x].l=l,t[x].r=r,t[x].len=r-l+1,t[x].to=none;
    if(l==r){
        t[x].maxx=a[x];
        return ;
    }
    int mid=(l+r)>>1;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);
} 
void cpushdown(int x){
    if(t[x].to!=none){
        //printf("%lld\n",t[x].to);
        t[x*2].add=t[x*2+1].add=0;
        t[x*2].maxx=t[x*2+1].maxx=t[x].to;
        t[x*2].to=t[x*2+1].to=t[x].to;
        t[x].to=none;
    }
}
void apushdown(int x){
    if(t[x].add){
        cpushdown(x);
        t[x*2].maxx+=t[x].add;
        t[x*2+1].maxx+=t[x].add;
        t[x*2].add+=t[x].add;
        t[x*2+1].add+=t[x].add;
        t[x].add=0;
    }
}
void pushdown(int x){
    cpushdown(x);
    apushdown(x);
}
int query(int x,int l,int r){
    int L=t[x].l,R=t[x].r;
    if(L>=l&&R<=r)return t[x].maxx;
    int mid=(L+R)>>1,val=0;
    pushdown(x);
    if(l<=mid)val=max(val,query(x*2,l,r)); 
    if(r>mid)val=max(val,query(x*2+1,l,r)); 
    return val; 
}
void changeto(int x,int l,int r,int k){
    int L=t[x].l,R=t[x].r;
    if(L>=l&&R<=r){
        t[x].add=0;
        t[x].maxx=k;
        t[x].to=k;
        return ;
    }
    pushdown(x);
    int mid=(L+R)>>1;
    if(l<=mid)changeto(x*2,l,r,k);
    if(r>mid)changeto(x*2+1,l,r,k);
    pushup(x);
}
void changeadd(int x,int l,int r,int k){
    int L=t[x].l,R=t[x].r;
    if(L>=l&&R<=r){
        cpushdown(x);
        t[x].maxx+=k;
        t[x].add+=k;
        return ;
    }    
    pushdown(x);
    int mid=(L+R)>>1;
    if(l<=mid)changeadd(x*2,l,r,k);
    if(r>mid)changeadd(x*2+1,l,r,k);
    pushup(x);
}
signed main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        int op;
        scanf("%lld",&op);
        if(op==1){
            int l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            changeto(1,l,r,x);
        }
        if(op==2){
            int l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            changeadd(1,l,r,x);
        }
        if(op==3){
            int l,r;
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(1,l,r)); 
        }
    }
    return 0;
} 

by peterwuyihong @ 2023-05-07 16:53:43

        t[x].maxx=a[x];

这个改完后还有问题

by peterwuyihong @ 2023-05-07 16:56:46

然后你query里的val改到LLONG_MIN避免负数情况，还有一个RE不知道咋回事，但好像把MAXN改大就行了

by lcbridge @ 2023-05-07 16:58:48

@peterwuyihong 请问LLONG_MIN 是啥？

by peterwuyihong @ 2023-05-07 16:59:25

哦，那个RE是你changeRE函数里进入分支节点的时候cpushdown导致的，去掉就行了，不是必要的

by peterwuyihong @ 2023-05-07 16:59:55

@Super_Dabubu 数据有负数，你要设一个负无穷大

by LgxTpre @ 2023-05-07 17:01:31

@Super_Dabubu none 设的有问题，综上改成这样

#include <bits/stdc++.h>
#define int long long
#define MAXN 1000005
#define none LLONG_MIN
using namespace std;
int n,q,a[MAXN];
struct SegmentTree{
    int l,r,len,maxx;
    int add,to;
}t[MAXN*4];
void pushup(int x){
    t[x].maxx=max(t[x*2].maxx,t[x*2+1].maxx);
}
void build(int x,int l,int r){
    t[x].l=l,t[x].r=r,t[x].len=r-l+1,t[x].to=none;
    if(l==r){
        t[x].maxx=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);
} 
void cpushdown(int x){
    if(t[x].to!=none){
        //printf("%lld\n",t[x].to);
        t[x*2].add=t[x*2+1].add=0;
        t[x*2].maxx=t[x*2+1].maxx=t[x].to;
        t[x*2].to=t[x*2+1].to=t[x].to;
        t[x].to=none;
    }
}
void apushdown(int x){
    if(t[x].add){
        t[x*2].maxx+=t[x].add;
        t[x*2+1].maxx+=t[x].add;
        t[x*2].add+=t[x].add;
        t[x*2+1].add+=t[x].add;
        t[x].add=0;
    }
}
void pushdown(int x){
    cpushdown(x);
    apushdown(x);
}
int query(int x,int l,int r){
    int L=t[x].l,R=t[x].r;
    if(L>=l&&R<=r)return t[x].maxx;
    int mid=(L+R)>>1,val=LLONG_MIN;
    pushdown(x);
    if(l<=mid)val=max(val,query(x*2,l,r)); 
    if(r>mid)val=max(val,query(x*2+1,l,r)); 
    return val; 
}
void changeto(int x,int l,int r,int k){
    int L=t[x].l,R=t[x].r;
    if(L>=l&&R<=r){
        t[x].add=0;
        t[x].maxx=k;
        t[x].to=k;
        return ;
    }
    pushdown(x);
    int mid=(L+R)>>1;
    if(l<=mid)changeto(x*2,l,r,k);
    if(r>mid)changeto(x*2+1,l,r,k);
    pushup(x);
}
void changeadd(int x,int l,int r,int k){
    int L=t[x].l,R=t[x].r;
    if(L>=l&&R<=r){
        t[x].maxx+=k;
        t[x].add+=k;
        return ;
    }    
    pushdown(x);
    int mid=(L+R)>>1;
    if(l<=mid)changeadd(x*2,l,r,k);
    if(r>mid)changeadd(x*2+1,l,r,k);
    pushup(x);
}
signed main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        int op;
        scanf("%lld",&op);
        if(op==1){
            int l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            changeto(1,l,r,x);
        }
        if(op==2){
            int l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            changeadd(1,l,r,x);
        }
        if(op==3){
            int l,r;
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(1,l,r)); 
        }
    }
    return 0;
} 

by lcbridge @ 2023-05-07 17:02:43

@peterwuyihong thx

by lcbridge @ 2023-05-07 17:02:53

@LgxTpre thx