线段树50pts求调

#include<bits/stdc++.h>
long long int a[1000005],d[4000025],cov[4000025],add[4000025];
bool c[4000025];//a为原数组，d为线段树数组，cov为覆盖标记，add为加法标记，c为当前的覆盖标记是否有效
int n,q;
long long int max(long long int a,long long int b){
    return a>b ? a : b;
}
#define lc (id<<1)
#define rc ((id<<1)+1)
#define mid ((r+l)>>1)
void build(int id,int l,int r){
    if(l == r)
        d[id] = a[l];
    else{
        build(lc,l,mid);
        build(rc,mid+1,r);
        d[id] = max(d[lc],d[rc]);
    }
    return;
}
void pushdown(int id,int l,int r){
    if(c[id]){
        d[lc] = cov[id],d[rc] = cov[id];
        if(l != mid)
            cov[lc] = cov[id],add[lc] = 0,c[lc] = 1;
        if(mid+1 != r)
            cov[rc] = cov[id],add[rc] = 0,c[rc] = 1;
    }
    d[lc] += add[id],d[rc] += add[id];
    if(l != mid)
        add[lc] += add[id];
    if(mid+1 != r)
        add[rc] += add[id];
    c[id] = 0,add[id] = 0;
    return;
}
void modify_cov(int id,int l,int r,int s,int e,int x){
    if(l == r)
        d[id] = x;
    else{
        if(s <= l && e >= r)
            d[id] = x,cov[id] = x,add[id] = 0,c[id] = 1;
        else{
            pushdown(id,l,r);
            if(s <= mid)
                modify_cov(lc,l,mid,s,e,x);
            if(e > mid)
                modify_cov(rc,mid+1,r,s,e,x);
            d[id] = max(d[lc],d[rc]);
        }
    }
    return;
}
void modify_add(int id,int l,int r,int s,int e,int x){
    if(l == r)
        d[id] += x;
    else{
        if(s <= l && e >= r)
            d[id] += x,add[id] += x;
        else{
            pushdown(id,l,r);
            if(s <= mid)
                modify_add(lc,l,mid,s,e,x);
            if(e > mid)
                modify_add(rc,mid+1,r,s,e,x);
            d[id] = max(d[lc],d[rc]);
        }
    }
    return;
}
long long int query(int id,int l,int r,int s,int e){
    if(s <= l && e >= r)
        return d[id];
    else{
        long long int ret = -1000000005;
        pushdown(id,l,r);
        if(s <= mid)
            ret = max(query(lc,l,mid,s,e),ret);
        if(e > mid)
            ret = max(query(rc,mid+1,r,s,e),ret);
        return ret;
    }
}
#undef lc
#undef rc
#undef mid
int main(void){
    int op,l,r,x;
    scanf("%d%d",&n,&q);
    for(int i = 1;i <= n;++ i)
        scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i = 1;i <= q;++ i){
        scanf("%d%d%d",&op,&l,&r);
        switch(op){
            case 1:
                scanf("%d",&x);
                modify_cov(1,1,n,l,r,x);
                break;
            case 2:
                scanf("%d",&x);
                modify_add(1,1,n,l,r,x);
                break;
            case 3:
                printf("%lld\n",query(1,1,n,l,r));
        }
    }
    return 0;
}