60pts求调

P1253 扶苏的问题

Purple_meteor @ 2023-11-29 12:56:31

WA了7-9,TLE了10,求大佬帮看看

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[10000001],ans[10000001],tag[10000001],tag_fix[10000001];
bool fix[10000001];
ll ls(ll x)
{
    return x<<1;
}
ll rs(ll x)
{
    return x<<1|1;
}
void push_up(ll p)
{
    ans[p]=max(ans[ls(p)],ans[rs(p)]);
}
void push_down(ll p,ll l,ll r)
{
    if(fix[p])
    {
        tag[p]=0;
        tag[ls(p)]=0;
        tag[rs(p)]=0;
        ans[ls(p)]=tag_fix[p];
        ans[rs(p)]=tag_fix[p];
        tag_fix[ls(p)]=tag_fix[p];
        tag_fix[rs(p)]=tag_fix[p];
        tag_fix[p]=0;
        fix[p]=0;
        fix[ls(p)]=1;
        fix[rs(p)]=1;
    }
    if(tag[p])
    {
        ans[ls(p)]+=tag[p];
        ans[rs(p)]+=tag[p];
        tag[ls(p)]+=tag[p];
        tag[rs(p)]+=tag[p];
        tag[p]=0;
    }
}
void build(ll p,ll l,ll r)
{
    tag[p]=0;
    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 add(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
    if(nl<=l&&r<=nr)
    {
        if(fix[p])
        {
            tag[p]=0;
            tag[ls(p)]=0;
            tag[rs(p)]=0;
            ans[ls(p)]=tag_fix[p];
            ans[rs(p)]=tag_fix[p];
            tag_fix[ls(p)]=tag_fix[p];
            tag_fix[rs(p)]=tag_fix[p];
            tag_fix[p]=0;
            fix[p]=0;
            fix[ls(p)]=1;
            fix[rs(p)]=1;
        }
        ans[p]+=k;
        tag[p]+=k;
        return ;
    }
    push_down(p,l,r);
    ll mid=(r+l)>>1;
    if(nl<=mid) add(nl,nr,l,mid,ls(p),k);
    if(nr>mid) add(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
void fit(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
    if(nl<=l&&r<=nr)
    {
        ans[p]=k;
        tag[p]=0;
        tag_fix[p]=k;
        fix[p]=1;
        return ;
    }
    push_down(p,l,r);
    ll mid=(r+l)>>1;
    if(nl<=mid) fit(nl,nr,l,mid,ls(p),k);
    if(nr>mid) fit(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
ll check(ll nl,ll nr,ll l,ll r,ll p)
{
    ll res=LONG_LONG_MIN;
    if(nl<=l&&r<=nr) return ans[p];
    push_down(p,l,r);
    ll mid=(r+l)>>1;
    if(nl<=mid) res=max(res,check(nl,nr,l,mid,ls(p)));
    if(nr>mid) res=max(res,check(nl,nr,mid+1,r,rs(p)));
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int c;
        cin>>c;
        switch(c)
        {
            case 1:
            {
                ll x,y,k;
                cin>>x>>y>>k;
                fit(x,y,1,n,1,k);
                break;
            }
            case 2:
            {
                ll x,y,k;
                cin>>x>>y>>k;
                add(x,y,1,n,1,k);
                break;
            }
            case 3:
            {
                ll x,y;
                cin>>x>>y;
                cout<<check(x,y,1,n,1)<<'\n';
                break;
            }
        }
    }
    return 0; 
} 

|