90pts,就#10WA了,求助求助

P1253 扶苏的问题

z262388814 @ 2022-10-28 11:31:50

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+10;
#define  inf 1e18

ll n,p;
ll a[maxn];
ll tr[4*maxn],laz[4*maxn],laz2[4*maxn];

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void build(ll k,ll l,ll r){
    if(l==r)
    { 
        tr[k] = a[l];
        laz2[k] = -1145141919180;
        laz[k] = 0;
        return;
    }

    ll mid = (l+r) / 2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    tr[k] = max(tr[k*2],tr[k*2+1]);
}

void cdown(ll k,ll l,ll r){ 
    if(laz2[k] != inf)
     {
        laz[k*2] = laz[k*2+1] = 0;
        laz2[k*2] = laz2[k*2+1] = laz2[k];
        tr[k*2] = tr[k*2+1] = laz2[k];

        laz2[k] = inf; 
     }
}

void sdown(ll k,ll l,ll r){
    if(laz[k])
    {
        cdown(k,l,r);
        laz[k*2] += laz[k];
        laz[k*2+1] += laz[k];
        tr[k*2] += laz[k];
        tr[k*2+1] += laz[k];
        laz[k] = 0;
    }
}

void pushdown(ll k,ll l,ll r){
     cdown(k,l,r);
     sdown(k,l,r);
}

ll query(ll k,ll l,ll r,ll x,ll y){
    if(x<=l && r<=y)    
        return tr[k];

    pushdown(k,l,r);
    ll mid = (l+r)/2;
    ll res  = -inf;
    if(x<=mid)  res = max(res,query(k*2,l,mid,x,y));
    if(mid+1<=y)    res = max(res,query(k*2+1,mid+1,r,x,y));

    return res;
}

void modify1(ll k,ll l,ll r,ll x,ll y,ll z){
    if(x<=l && r<=y)
    {
        laz[k] = 0;
        tr[k] = laz2[k] = z;
        return;
    }

    pushdown(k,l,r);
    ll mid = (l+r) / 2;
    if(x<=mid)  modify1(k*2,l,mid,x,y,z);
    if(mid<y)   modify1(k*2+1,mid+1,r,x,y,z);
    tr[k] = max(tr[k*2],tr[k*2+1]);
}

void modify2(ll k,ll l,ll r,ll x,ll y,ll z){
    if(x<=l && r<=y)
    {
        cdown(k,l,r);
        laz[k] += z;
        tr[k] +=z;
        return;
    }

    pushdown(k,l,r);
    ll mid = (l+r)/2;
    if(x<=mid)  modify2(k*2,l,mid,x,y,z);
    if(mid<y)   modify2(k*2+1,mid+1,r,x,y,z);
    tr[k] = max(tr[k*2],tr[k*2+1]);
}

int main(){
    scanf("%lld%lld",&n,&p);
    for(ll i=1;i<=n;++i)
        a[i] = read();
    build(1,1,n);
    for(ll i=1;i<=4*n;++i)
        laz2[i] = inf;

    while(p--) 
    {
        ll f,x,y;
        f=read(),x=read(),y=read();
        //cout << f << " " << x << " " << y << endl;
         if(f==1)
        {
            ll z=read();
            modify1(1,1,n,x,y,z); 
        }
        else if(f==2){
            ll z=read();
            modify2(1,1,n,x,y,z);
        }
        else
        {   
            //cout << "asdchaoiunc" << endl;
            printf("%lld\n",query(1,1,n,x,y));
        }

    }
    return 0;
}

|