线段树 90pts WA#10（1.77s） 求调

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
    short f=1;ll x=0;char s=getchar();
    while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
    while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
    return x*f;
}
const ll kksk=-111111111111111111;
ll a[1000001],ans[1000001<<2],slt[1000001<<2],clt[1000001<<2];
ll ls(ll p){return p<<1;}ll rs(ll p){return p<<1|1;}
void push_up(ll p){ans[p]=max(ans[ls(p)],ans[rs(p)]);}
void build(ll p,ll l,ll r)
{
    slt[p]=0;clt[p]=kksk;
    if(l==r){ans[p]=a[l];return;}
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void cdf_push_down(ll p)
{
    if(clt[p]!=kksk)
    {
        clt[ls(p)]=clt[p];clt[rs(p)]=clt[p];
        ans[ls(p)]=clt[p];ans[rs(p)]=clt[p];
        slt[ls(p)]=0;slt[rs(p)]=0;clt[p]=kksk;
    }
}
void sf_push_down(ll p)
{
    if(slt[p])
    {
        cdf_push_down(p);
        slt[ls(p)]=slt[ls(p)]+slt[p];
        slt[rs(p)]=slt[rs(p)]+slt[p];
        ans[ls(p)]=ans[ls(p)]+slt[p];
        ans[rs(p)]=ans[rs(p)]+slt[p];
        slt[p]=0;
    }
}
void push_down(ll p){cdf_push_down(p);sf_push_down(p);}
void pls_update(ll p,ll nl,ll nr,ll l,ll r,ll k)
{
    if(nl<=l&&r<=nr){cdf_push_down(p);
    slt[p]=slt[p]+k;ans[p]=ans[p]+k;return;}
    push_down(p);ll mid=(l+r)>>1;
    if(nl<=mid)pls_update(ls(p),nl,nr,l,mid,k);
    if(nr>mid)pls_update(rs(p),nl,nr,mid+1,r,k);
    push_up(p);
}
void cg_update(ll p,ll nl,ll nr,ll l,ll r,ll k)
{
    if(nl<=l&&r<=nr){slt[p]=0;clt[p]=k;ans[p]=k;return;}
    push_down(p);ll mid=(l+r)>>1;
    if(nl<=mid)cg_update(ls(p),nl,nr,l,mid,k);
    if(nr>mid)cg_update(rs(p),nl,nr,mid+1,r,k);
    push_up(p);
}
ll query(ll p,ll qx,ll qy,ll l,ll r)
{
    if(qx<=l&&r<=qy)return ans[p];
    push_down(p);ll mx=kksk,mid=(l+r)>>1;
    if(qx<=mid)mx=max(mx,query(ls(p),qx,qy,l,mid));
    if(qy>mid)mx=max(mx,query(rs(p),qx,qy,mid+1,r));
    return mx;
}
int main()
{
    int n=read(),m=read();ll k,x,y,z;
    for(int i=1;i<=n;++i)a[i]=read();
    build(1,1,n);
    while(m--)
    {
        k=read();
        if(k==1)
        {
            x=read();y=read();z=read();
            cg_update(1,x,y,1,n,z);
        }
        else if(k==2)
        {
            x=read();y=read();z=read();
            pls_update(1,x,y,1,n,z);
        }
        else
        {
            x=read();y=read();
            z=query(1,x,y,1,n);
            printf("%lld\n",z);
        }
    }
    return 0;
}