20分求调

P1253 扶苏的问题

Amon_Xolotl @ 2023-07-04 19:44:23

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll n,q,a[N];
struct zjy
{
    ll lazy,maxn,tag;
}tree[N<<2];
void pushup(int rt)
{
    tree[rt].maxn=max(tree[rt<<1].maxn,tree[rt<<1|1].maxn);
}
void build(ll rt,ll l,ll r)
{
    tree[rt].lazy=0;
    tree[rt].tag=-1000000000000000;
    if(l==r)
    {
        tree[rt].maxn=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void pushdown1(ll rt)
{
    if(tree[rt].tag!=-1000000000000000)
    {
        tree[rt<<1|1].maxn=tree[rt<<1].maxn=tree[rt].tag;
        tree[rt<<1].lazy=tree[rt<<1|1].lazy=0;
        tree[rt<<1|1].tag=tree[rt<<1].tag=tree[rt].tag;
        tree[rt].tag=-1000000000000000;
    }
}

void pushdown2(ll rt)
{
    if(tree[rt].lazy)
    {
        pushdown1(rt);
        tree[rt<<1].maxn+=tree[rt].lazy;
        tree[rt<<1|1].maxn+=tree[rt].lazy;
        tree[rt<<1].lazy+=tree[rt].lazy;
        tree[rt<<1|1].lazy+=tree[rt].lazy;
        tree[rt].lazy=0;
    }
}
void pushdown(ll rt)
{
    pushdown1(rt),pushdown2(rt);
}
void modify(ll rt,ll l,ll r,ll x,ll y,ll v)
{
    if(l>=x&&r<=y)
    {

        tree[rt].maxn=v;
        tree[rt].tag=v;
        tree[rt].lazy=0;
        return;
    }
    ll mid=(l+r)>>1;
    pushdown(rt);
    if(x<=mid)
    {
        modify(rt<<1,l,mid,x,y,v);
    }
    if(y>mid)
    {
        modify(rt<<1|1,mid+1,r,x,y,v);
    }
    pushup(rt);
}
void update(ll rt,ll l,ll r,ll x,ll y,ll v)
{
    if(l>=x&&r<=y)
    {
        pushdown1(rt);
        tree[rt].lazy+=v;
        tree[rt].maxn+=v;
        return;
    }
    ll mid=(l+r)>>1;
    pushdown(rt);
    if(x<=mid)
    {
        update(rt<<1,l,mid,x,y,v);
    }
    if(y>mid)
    {
        update(rt<<1|1,mid+1,r,x,y,v);
    }
    pushup(rt);
}
ll ask(ll rt,ll l,ll r,ll x,ll y)
{
    if(l>=x&&r<=y)
    {
        return tree[rt].maxn;
    }
    ll ans=-1000000000000000;
    ll mid=(l+r)>>1;
    if(x<=mid)
    {
        ans=max(ans,ask(rt<<1,l,mid,x,y));
    }
    if(y>mid)
    {
           ans=max(ans,ask(rt<<1|1,mid+1,r,x,y));
    }
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while(q--)
    {
        ll opt,l,r;
        scanf("%lld%lld%lld",&opt,&l,&r);
        if(opt==1)
        {
            ll x;
            scanf("%lld",&x);
            modify(1,1,n,l,r,x);
        }
        else if(opt==2)
        {
            ll x;
            scanf("%lld",&x);
            update(1,1,n,l,r,x);
        }
        else if(opt==3)
        {
            printf("%lld\n",ask(1,1,n,l,r));
        }
    }
    return 0;
}

|