线段树50pts求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+5;
const ll RR=-1e15;
ll A[maxn];
struct SegmentTree{
    #define ls (rt<<1)
    #define rs (rt<<1|1)
    struct tag{
        ll cover,add;
    }Tag[maxn<<2];
    int Data[maxn<<2];
    inline void PushUp(int rt)
    {
        Data[rt]=max(Data[ls],Data[rs]);
    }
    inline void PushDown_C(int l,int r,int rt)
    {
        if(Tag[rt].cover!=RR)
        {
            Data[ls]=Data[rs]=Tag[ls].cover=Tag[rs].cover=Tag[rt].cover;
            Tag[rt].cover=RR;
            Tag[ls].add=Tag[rs].add=0;
        }
    }
    inline void PushDown_A(int l,int r,int rt)
    {
        if(Tag[rt].add)
        {
            Data[ls]+=Tag[rt].add;
            Data[rs]+=Tag[rt].add;
            Tag[ls].add+=Tag[rt].add;
            Tag[rs].add+=Tag[rt].add;
            Tag[rt].add=0;
        }
    }
    inline void Build(int l,int r,int rt)
    {
        Tag[rt].cover=RR;
        Tag[rt].add=0;
        if(l==r)
        {
            Data[rt]=A[l];
            return ;
        }
        int m=(l+r)>>1;
        Build(l,m,ls);
        Build(m+1,r,rs);
        PushUp(rt);
    }
    inline void Upd_C(int L,int R,ll C,int l,int r,int rt)
    {
        if(L==l&&R==r)
        {
            Data[rt]=C;
            Tag[rt].cover=C;
            Tag[rt].add=0;
            return ;
        }
        PushDown_C(l,r,rt);
        PushDown_A(l,r,rt);
        int m=(l+r)>>1;
        if(R<=m)
            Upd_C(L,R,C,l,m,ls);
        else if(L>=m+1)
            Upd_C(L,R,C,m+1,r,rs);
        else
        {
            Upd_C(L,m,C,l,m,ls);
            Upd_C(m+1,R,C,m+1,r,rs);
        }
        PushUp(rt);
    }
    inline void Upd_A(int L,int R,ll C,int l,int r,int rt)
    {
        if(L==l&&R==r)
        {
            Data[rt]+=C;
            Tag[rt].add+=C;
            return ;
        }
        PushDown_C(l,r,rt);
        PushDown_A(l,r,rt);
        int m=(l+r)>>1;
        if(R<=m)
            Upd_A(L,R,C,l,m,ls);
        else if(L>=m+1)
            Upd_A(L,R,C,m+1,r,rs);
        else
        {
            Upd_A(L,m,C,l,m,ls);
            Upd_A(m+1,R,C,m+1,r,rs);
        }
        PushUp(rt);
    }
    inline ll Query(int L,int R,int l,int r,int rt)
    {
        if(L==l&&R==r)
            return Data[rt];
        PushDown_C(l,r,rt);
        PushDown_A(l,r,rt);
        int m=(l+r)>>1;
        if(R<=m)
            return Query(L,R,l,m,ls);
        else if(L>=m+1)
            return Query(L,R,m+1,r,rs);
        else
            return max(Query(L,m,l,m,ls),Query(m+1,R,m+1,r,rs));
    }
}Seg;
signed main()
{
    int n,q,op,l,r;
    ll x;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%lld",&A[i]);
    Seg.Build(1,n,1);
    while(q--)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)
        {
            scanf("%lld",&x);
            Seg.Upd_C(l,r,x,1,n,1);
        }
        else if(op==2)
        {
            scanf("%lld",&x);
            Seg.Upd_A(l,r,x,1,n,1);
        }
        else
            printf("%lld\n",Seg.Query(l,r,1,n,1));
    }
    exit(puts("")&0);
}