线段树20PTS求调

#include<bits/stdc++.h>
#define ll long long
#define lson pos<<1 
#define rson pos<<1|1
using namespace std;
const int maxn=1e6+10;
const int mod=1e6+7;
int n;
ll m,t;
int a[maxn];
struct node{
    ll add,mx,re;
}tree[maxn*4];

void pushup(int pos){
    tree[pos].mx=max(tree[lson].mx,tree[rson].mx);
    return;
}

void pushdown(int pos,int l,int r){
    //cout<<l<<" "<<r<<" "<<tree[pos].re<<" "<<tree[pos].add<<" "<<tree[pos].mx<<endl;
    if(l==r) {tree[pos].add=0;tree[pos].re=1000000001;return;}
    if(tree[pos].re!=1000000001){
        tree[lson].mx=tree[rson].mx=tree[pos].re;
        tree[lson].re=tree[rson].re=tree[pos].re;
        tree[lson].add=tree[rson].add=0;
        tree[pos].re=1000000001;
        return;
    }
    if(tree[pos].add==0) return;
    tree[lson].mx+=tree[pos].add;
    tree[rson].mx+=tree[pos].add;
    tree[lson].add+=tree[pos].add;
    tree[rson].add+=tree[pos].add;
    return;
}

void build(int pos,int l,int r){
    if(l==r){
        tree[pos].re=1000000001;
        tree[pos].add=0;
        tree[pos].mx=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(pos);
    return;
}

void change(int pos,int l,int r,int xl,int xr,int k){
    if(xl<=l&&r<=xr){
        tree[pos].re=tree[pos].mx=k;
        tree[pos].add=0;
        return;
    }
    pushdown(pos,l,r);
    int mid=(l+r)/2;
    if(xl<=mid) change(lson,l,mid,xl,xr,k);
    if(xr>mid) change(rson,mid+1,r,xl,xr,k);
    pushup(pos);
    return;
}

void plu(int pos,int l,int r,int xl,int xr,int k){
    pushdown(pos,l,r);
    if(xl<=l&&xr>=r){
        tree[pos].add+=k;
        tree[pos].mx+=k;
        return;
    }   
    int mid=(l+r)/2;
    if(xl<=mid) plu(lson,l,mid,xl,xr,k);
    if(xr>mid) plu(rson,mid+1,r,xl,xr,k);
    pushup(pos);
    return;
}

ll query(int pos,int l,int r,int xl,int xr){
    pushdown(pos,l,r);
    if(xl<=l&&r<=xr){
        return tree[pos].mx;
    }
    int mid=(l+r)/2;
    ll res=0;
    if(xl<=mid) res=max(res,query(lson,l,mid,xl,xr));
    if(xr>mid) res=max(res,query(rson,mid+1,r,xl,xr));
    return res;
}

int main(){
    scanf("%d%d",&n,&m);    
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--){
        int order,x,y,z;
        scanf("%d",&order);
        if(order==1){
            scanf("%d%d%d",&x,&y,&z);
            change(1,1,n,x,y,z);
        }
        else if(order==2){
            scanf("%d%d%d",&x,&y,&z);
            plu(1,1,n,x,y,z);
        }
        else{
            scanf("%d%d",&x,&y);
            ll res=query(1,1,n,x,y);
            printf("%lld\n",res);
        }
    }
    return 0;
}