线段树爆零求救

P4513 小白逛公园

yinbe @ 2023-12-15 22:38:01

#include<iostream>
using namespace std;
struct tree
{
    int l,r;
    long long dat,sum,lmax,rmax;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define sum(x) t[x].sum
    #define lmax(x) t[x].lmax
    #define rmax(x) t[x].rmax
    #define dat(x) t[x].dat
}t[2000005];
int n,m,a[500005];
void build(int p,int l,int r)
{
    l(p)=l,r(p)=r;
    if(l==r)
    {
        sum(p)=a[l];
        lmax(p)=a[l];
        rmax(p)=a[l];
        dat(p)=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=sum(p*2)+sum(p*2+1);
    lmax(p)=max(lmax(p*2),sum(p*2)+lmax(p*2+1));
    rmax(p)=max(rmax(p*2+1),sum(p*2+1)+rmax(p*2));
    dat(p)=max(dat(p*2),max(dat(p*2+1),rmax(p*2)+lmax(p*2+1)));
    return;
}
void change(int p,int x,int d)
{
    if(l(p)==r(p))
    {
        sum(p)=d;
        lmax(p)=d;
        rmax(p)=d;
        dat(p)=d;
        return;     
    }
    int mid=(l(p)+r(p))>>1;
    if(x<=mid)change(p*2,x,d);
    else change(p*2+1,x,d);
    sum(p)=sum(p*2)+sum(p*2+1);
    lmax(p)=max(lmax(p*2),sum(p*2)+lmax(p*2+1));
    rmax(p)=max(rmax(p*2+1),sum(p*2+1)+rmax(p*2));
    dat(p)=max(dat(p*2),max(dat(p*2+1),rmax(p*2)+lmax(p*2+1)));
    return; 
}
long long ask(int p,int l,int r)
{
    if(l<=l(p)&&r>=r(p))
    {
        return dat(p); 
    }
    int mid=(l(p)+r(p))>>1;
    long long Max=-500000005;
    if(l<=mid)Max=max(Max,ask(p*2,l,r));
    if(r>mid)Max=max(Max,ask(p*2+1,l,r));
    return Max;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--)
    {
        int flag;
        scanf("%d",&flag);
        if(flag==1)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            if(l>r)swap(l,r);
            printf("%lld\n",ask(1,l,r));
        }
        else
        {
            int x,d;
            scanf("%d%d",&x,&d);
            change(1,x,d);
        }
    }
    return 0;
}

|