蒟蒻刚学oi，线段树40求调。

Chicken_Rrog @ 2022-10-27 18:49:43

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1000005],op,x,y,k;
struct tree{
    long long l,r,mx,lz1,lz2;
}t[4000005];
inline void build(long long i,long long l,long long r){
    t[i].l=l,t[i].r=r;
    if(l==r){
        t[i].mx=a[l];
        return;
    }
    long long mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    t[i].mx=max(t[i<<1].mx,t[i<<1|1].mx);
    return;
}
inline void push_down(long long i){
    if(t[i].lz1){
        t[i<<1].lz2=0;
        t[i<<1|1].lz2=0;
        t[i<<1].lz1=t[i].lz1;
        t[i<<1|1].lz1=t[i].lz1;
        t[i<<1].mx=t[i].lz1;
        t[i<<1|1].mx=t[i].lz1;
        t[i].lz1=0;
    }else{
        t[i<<1].lz2+=t[i].lz2;
        t[i<<1|1].lz2+=t[i].lz2;
        t[i<<1].mx+=t[i].lz2;
        t[i<<1|1].mx+=t[i].lz2;
        t[i].lz2=0;
    }
    return;
}
inline void add1(long long i,long long l,long long r,long long k){
    if(t[i].l>=l&&t[i].r<=r){
        t[i].mx=k;
        t[i].lz1=k;
        t[i].lz2=0;
        return;
    }
    push_down(i);
    if(t[i<<1].r>=l) add1(i<<1,l,r,k);
    if(t[i<<1|1].l<=r) add1(i<<1|1,l,r,k);
    t[i].mx=max(t[i<<1].mx,t[i<<1|1].mx);
    return;
}
inline void add2(long long i,long long l,long long r,long long k){
    if(t[i].l>=l&&t[i].r<=r){
        t[i].mx+=k;
        if(t[i].lz1!=0) t[i].lz1+=k;
        else t[i].lz2+=k;
        return;
    }
    push_down(i);
    if(t[i<<1].r>=l) add2(i<<1,l,r,k);
    if(t[i<<1|1].l<=r) add2(i<<1|1,l,r,k);
    t[i].mx=max(t[i<<1].mx,t[i<<1|1].mx);
    return;
}
inline long long search(long long i,long long l,long long r){
    if(t[i].l>=l&&t[i].r<=r) return t[i].mx;
    push_down(i);
    long long num=-1;
    if(t[i<<1].r>=l) num=search(i<<1,l,r);
    if(t[i<<1|1].l<=r) num=max(num,search(i<<1|1,l,r));
    return num;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1){
            scanf("%lld",&k);
            add1(1,x,y,k);
        }else if(op==2){
            scanf("%lld",&k);
            add2(1,x,y,k);
        }else{
            printf("%lld\n",search(1,x,y));
        }
    }
    return 0;
}

by Sidebyside_ @ 2022-10-27 19:14:51

这边建议将覆盖和修改的pushdown分开写

by simple_line @ 2022-10-27 20:46:49

错的地方有点多，于是我给你重构了一下，可以参考下

#include<bits/stdc++.h>
#define int long long
#define LL long long
using namespace std;
const LL inf=1e18;
long long n,m,a[1000005],op,x,y,k;
struct tree{
    LL mx,lz1,lz2;        //lz1覆盖，lz2加 
}t[4000005];
void build(int id,int l,int r)
{
    t[id].lz1=inf;
    t[id].lz2=0;
    if(l==r)
    {
        t[id].mx=a[l];return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    t[id].mx=max(t[id<<1].mx,t[id<<1|1].mx);
}
void pushdown(int id,int t1,int t2)
{
    if(t1!=inf)
    {
        t[id].mx=t[id].lz1=t1;
        t[id].lz2=0;
    }
    if(t2!=0)
    {
        t[id].mx+=t2;
        t[id].lz2+=t2;
    }
}
void spread(int id)
{
    pushdown(id<<1,t[id].lz1,t[id].lz2);
    pushdown(id<<1|1,t[id].lz1,t[id].lz2);
    t[id].lz1=inf;
    t[id].lz2=0;
}
void modefy_cov(int id,int l,int r,int x,int y,int c)
{
    if(x<=l&&r<=y)
    {
        t[id].lz1=t[id].mx=c;
        t[id].lz2=0;
        return;
    }
    spread(id);
    int mid=(l+r)>>1;
    if(x<=mid) modefy_cov(id<<1,l,mid,x,y,c);
    if(mid<y) modefy_cov(id<<1|1,mid+1,r,x,y,c);
    t[id].mx=max(t[id<<1].mx,t[id<<1|1].mx); 
}
void modefy_add(int id,int l,int r,int x,int y,int c)
{
    if(x<=l&&r<=y)
    {
        t[id].lz2+=c;
        t[id].mx+=c;
        return;
    }
    spread(id);
    int mid=(l+r)>>1;
    if(x<=mid) modefy_add(id<<1,l,mid,x,y,c);
    if(mid<y) modefy_add(id<<1|1,mid+1,r,x,y,c);
    t[id].mx=max(t[id<<1].mx,t[id<<1|1].mx);
}
LL query(int id,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return t[id].mx;
    spread(id);
    int mid=(l+r)>>1;LL res=-inf;
    if(x<=mid) res=query(id<<1,l,mid,x,y);
    if(mid<y) res=max(res,query(id<<1|1,mid+1,r,x,y));
    return res;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1){
            scanf("%lld",&k);
            modefy_cov(1,1,n,x,y,k);
        }else if(op==2){
            scanf("%lld",&k);
            modefy_add(1,1,n,x,y,k);
        }else{
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

by Chicken_Rrog @ 2022-10-27 20:50:43

@simple_line 抱歉，刚刚看到，谢谢了。