link

非常直白的线段树题目

要注意负数的问题以及吮吸

#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
int tree[8000002];
int lazyre[8000002];
int lazyad[8000002];
int n,q;
int op;
int minn;
int x,y,z;
void pushdown(int root,int l,int r){
    if(lazyre[root]!=minn){
        lazyad[root<<1]=0;
        lazyad[root<<1|1]=0;
        lazyre[root<<1]=lazyre[root];
        lazyre[root<<1|1]=lazyre[root];
        tree[root<<1]=tree[root<<1|1]=lazyre[root];
        lazyre[root]=minn;
    }
    if(lazyad[root]!=0){
        lazyad[root<<1]+=lazyad[root];
        lazyad[root<<1|1]+=lazyad[root];
        tree[root<<1]+=lazyad[root];
        tree[root<<1|1]+=lazyad[root];
        lazyad[root]=0;
    }

}
void pushup(int root){
    tree[root]=max(tree[root<<1],tree[root<<1|1]);
}
void add(int root,int l,int r,int L,int R,int v){
    if(L<=l&&r<=R){
        lazyad[root]+=v;
        tree[root]+=v;
        return ;
    }
    pushdown(root,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) add(root<<1,l,mid,L,R,v);
    if(R>mid) add(root<<1|1,mid+1,r,L,R,v);
    pushup(root);
}
void re(int root,int l,int r,int L,int R,int v){
    if(L<=l&&r<=R){
        lazyad[root]=0;
        lazyre[root]=v;
        tree[root]=v;
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(root,l,r);
    if(L<=mid) re(root<<1,l,mid,L,R,v);
    if(R>mid) re(root<<1|1,mid+1,r,L,R,v);
    pushup(root);
}
int ask(int root,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return tree[root];
    }
    pushdown(root,l,r);
    int mid=(l+r)>>1;
    int ans=minn;
    if(L<=mid) ans=max(ans,ask(root<<1,l,mid,L,R));
    if(R>mid) ans=max(ans,ask(root<<1|1,mid+1,r,L,R));
    pushup(root);
    return ans;
}
signed main(){
    scanf("%lld%lld",&n,&q);
    memset(lazyre,0xc0,sizeof(lazyre));
    minn=lazyre[0];
    //cout<<minn;
    for(int i=1;i<=n;++i){
        scanf("%lld",&x);
        add(1,1,n,i,i,x);
    }
    for(int i=1;i<=q;++i){
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld%lld",&x,&y,&z);
            re(1,1,n,x,y,z);
        }
        if(op==2){
            scanf("%lld%lld%lld",&x,&y,&z);
            add(1,1,n,x,y,z);
        }
        if(op==3){
            scanf("%lld%lld",&x,&y);
            cout<<ask(1,1,n,x,y)<<endl;
        }
    }
}