20pts萌新求调

P1253 扶苏的问题

BeBanned @ 2023-02-10 22:08:58

召唤大佬

#include <iostream>
#include <cstdio>
using namespace std;
#define INF 1e18
typedef long long ll;
const ll MAXN = 1000005;
ll n,m;
ll a[MAXN];
ll ma[MAXN << 2];
ll add[MAXN << 2];
ll cove[MAXN << 2];
inline ll lc(ll p)
{
    return p << 1;
}
inline ll rc(ll p)
{
    return p << 1 | 1;
}
void pushup(ll p)
{
    ma[p] = max(ma[lc(p)],ma[rc(p)]);
}
void buildTree(ll p,ll l,ll r)
{
    ma[p] = -INF;
    add[p] = 0;
    cove[p] = INF;
    if(l == r)
    {
        ma[p] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    buildTree(lc(p),l,mid);
    buildTree(rc(p),mid + 1,r);
    pushup(p);
}
void movetag(ll p,ll l,ll r,ll ad,ll co)
{
    if(co != INF) // 优先平推
    {
        cove[p] = co;
        add[p] = ad;
        ma[p] = co + ad;
    }
    else
    {
        add[p] += ad;
        ma[p] += ad;
    }
}
void pushdown(ll p,ll l,ll r)
{
    ll mid = (l + r) >> 1;
    movetag(lc(p),l,mid,add[p],cove[p]);
    movetag(rc(p),mid + 1,r,add[p],cove[p]);
    add[p] = 0;
    cove[p] = INF;
}
void update1(ll p,ll l,ll r,ll ql,ll qr,ll t) // 区间平推
{
    if(ql <= l && r <= qr)
    {
        ma[p] = t;
        cove[p] = t;
        add[p] = 0;
        return;
    }
    pushdown(p,l,r);
    ll mid = (l + r) >> 1;
    if(ql <= mid)
    {
        update1(lc(p),l,mid,ql,qr,t);
    }
    if(mid < qr)
    {
        update1(rc(p),mid + 1,r,ql,qr,t);
    }
    pushup(p);
}
void update2(ll p,ll l,ll r,ll ql,ll qr,ll t) // 区间加法
{
    if(ql <= l && r <= qr)
    {
        ma[p] += t;
        add[p] += t;
        return;
    }
    pushdown(p,l,r);
    ll mid = (l + r) >> 1;
    if(ql <= mid)
    {
        update2(lc(p),l,mid,ql,qr,t);
    }
    if(mid < qr)
    {
        update2(rc(p),mid + 1,r,ql,qr,t);
    }
    pushup(p);
}
ll query(ll p,ll l,ll r,ll ql,ll qr)
{
    if(ql <= l && r <= qr)
    {
        return ma[p];
    }
    ll mid = (l + r) >> 1;
    ll ans = -INF;
    if(ql <= mid)
    {
        ans = max(ans,query(lc(p),l,mid,ql,qr));
    }
    if(mid < qr)
    {
        ans = max(ans,query(rc(p),mid + 1,r,ql,qr));
    }
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(ll i = 1;i <= n;i ++)
    {
        scanf("%lld",&a[i]);
    }
    buildTree(1,1,n);
    while(m --)
    {
        ll oper;
        scanf("%lld",&oper);
        if(oper == 1)
        {
            ll l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            update1(1,1,n,l,r,x);
        }
        if(oper == 2)
        {
            ll l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            update2(1,1,n,l,r,x);
        }
        if(oper == 3)
        {
            ll l,r;
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(1,1,n,l,r));
        }
    }
    return 0;
}

by BeBanned @ 2023-02-11 08:55:27

A了,忘pushdown了。。


|