10pts,9re(应该是递归爆栈),求调

P1253 扶苏的问题

Coding_Zhouzehao @ 2022-08-12 21:33:34


#include<iostream>
#define ll long long
#define lc p << 1
#define rc p << 1 | 1
#define mid ((l + r) >> 1)
using namespace std;
const int MAXN = 1e6 + 5;
const ll inf = 1e18;
struct tree
{
    ll tag1,tag2;
    //tag1表示区间赋值为tag1
    //tag2表示区间加上tag2
    ll Max;
    int l,r;
    bool used;
} t[MAXN << 2];
int n, m;
ll a[MAXN];
void push_up(int p)
{
    t[p].Max = max(t[lc].Max,t[rc].Max);
}
void push_down(int p)
{
    if(t[p].used)//是否有tag1
    {
        t[lc].tag1 = t[rc].tag1 = t[p].tag1;
        t[lc].tag2 = t[rc].tag2 = t[p].tag2;
        t[lc].Max = t[rc].Max = t[p].tag1 + t[p].tag2;
        t[lc].used = t[rc].used = 1;
    }
    else 
    {
        t[lc].tag2 += t[p].tag2,t[rc].tag2 += t[p].tag2;
        t[lc].Max += t[p].tag2,t[rc].Max += t[p].tag2;
    }
    t[p].used = 0;
    t[p].tag1 = t[p].tag2 = 0;
}
void biuld(int p,int l,int r)
{
    t[p].l = l,t[p].r = r,t[p].Max = -inf;
    if(l == r)
    {
        t[p].Max = a[l];
        return;
    }
    biuld(lc,l,mid);biuld(rc,mid+1,r);
    push_up(p);
}
void change(int p,int l,int r,ll x)
{
    if(l <= t[p].l && t[p].r <= r)//完全被包含
    {
        t[p].tag1 = x,t[p].tag2 = 0;
        t[p].Max = x,t[p].used = 1;
        return;
    }
    if(l <= mid) change(lc,l,r,x);
    if(mid + 1 <= r)change(rc,l,r,x);
    push_up(p);
}
void add(int p,int l,int r,ll x)
{
    if(l <= t[p].l && t[p].r <= r)
    {
        t[p].tag2 += x,t[p].Max += x;
        return;
    }
    push_down(p);//标记下传
    if(l <= mid)add(lc,l,r,x);
    if(mid + 1 <= r)add(rc,l,r,x);
    push_up(p);
}
ll query(int p,int l,int r)
{
    if(l <= t[p].l && r <= t[p].r)
        return t[p].Max;
    push_down(p);
    ll ans = -inf;
    if(l <= mid) ans = max(ans,query(lc,l,r));
    if(mid + 1 <= r)ans = max(ans,query(rc,l,r));
    return ans;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",a+i);
    biuld(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,l,r;
        ll x;
        scanf("%d%d%d",&op,&l,&r);
        if(op == 1 || op == 2)
            scanf("%lld",&x);
        if(op == 1)
            change(1,l,r,x);
        else if(op == 2)
            add(1,l,r,x);
        else 
            printf("%lld\n",query(1,l,r));
    }
}

by Coding_Zhouzehao @ 2022-08-12 21:34:17

第一次尝试define的马蜂,可能搞了一堆bug


|