萌新线段树求调

60pts WA on #7~10

#include<bits/stdc++.h>
#define lc (k<<1)
#define rc (k<<1|1)
#define nul 0x7f7f7f7f7f7f7f7f7f
using namespace std;
typedef long long ll;
const int N=1e6;
int n,m,a[N+5];
ll maxn[N*2+5],lztag1[N*2+5],lztag2[N*2+5];
//tag1:赋值标记  tag2:增加标记 
void build(int k,int l,int r){
    if(l==r){
        maxn[k]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    maxn[k]=max(maxn[lc],maxn[rc]);
}
void pushdown(int k,int l,int r){
    if(lztag1[k]==nul&&!lztag2[k])return;
    if(lztag1[k]!=nul){//有赋值标记 
        maxn[lc]=lztag1[k];
        lztag1[lc]=lztag1[k];
        maxn[rc]=lztag1[k];
        lztag1[rc]=lztag1[k];
        lztag1[k]=nul;
    }
    if(lztag2[k]){//有增加标记 
        maxn[lc]+=lztag2[k];
        lztag2[lc]+=lztag2[k];
        maxn[rc]+=lztag2[k];
        lztag2[rc]+=lztag2[k];
        lztag2[k]=0;
    }
}
void change(int k,int l,int r,int x,int y,ll s,bool f){//f=0时代表赋值操作，f=1时代表增加操作 
    if(r<x||l>y)return;
    if(l==r){
        if(!f)maxn[k]=s;
        else maxn[k]+=s;
        return;
    }
    if(l>=x&&r<=y){
        if(!f){
            maxn[k]=s;
            lztag1[k]=s;
            lztag2[k]=0;
        }
        else{
            maxn[k]+=s;
            lztag2[k]+=s;
        }
        return;
    }
    int mid=l+r>>1;
    pushdown(k,l,r);
    change(lc,l,mid,x,y,s,f);
    change(rc,mid+1,r,x,y,s,f);
    maxn[k]=max(maxn[lc],maxn[rc]);
}
ll query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y)return maxn[k];
    int mid=l+r>>1;
    pushdown(k,l,r);
    if(y<=mid)return query(lc,l,mid,x,y);
    else if(x>=mid+1)return query(rc,mid+1,r,x,y);
    else return max(query(lc,l,mid,x,y),query(rc,mid+1,r,x,y));
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    build(1,1,n);
    fill(lztag1,lztag1+N*2+5,nul);
    for(int i=1;i<=m;i++){
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op<3){
            ll s;
            scanf("%lld",&s);
            change(1,1,n,l,r,s,op-1);
        }
        else
            printf("%lld\n",query(1,1,n,l,r));
    }
}