蒟蒻绝望求助,9分代码死也改不对

P4513 小白逛公园

xo_永夜_ox @ 2019-09-06 19:17:58

#include<bits/stdc++.h>
#define reg register
using namespace std;
const int maxx=500050;
int n,m,c[maxx];
struct node{
    int l,r,dat,sum,lmax,rmax;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define dat(x) t[x].dat
    #define sum(x) t[x].sum
    #define lm(x) t[x].lmax
    #define rm(x) t[x].rmax
}t[maxx<<2];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
    return s*w; 
}
inline void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    if(l==r){
        sum(p)=c[l];
        dat(p)=c[l];
        lm(p)=c[l];
        rm(p)=c[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=sum(p*2)+sum(p*2+1);
    lm(p)=max(lm(p*2),sum(p*2)+lm(p*2+1));
    rm(p)=max(rm(p*2+1),sum(p*2+1)+rm(p*2));
    dat(p)=max(max(lm(p*2),rm(p*2+1)),rm(p*2)+lm(p*2+1));
}
inline void change(int p,int x,int k){
    if(l(p)==r(p)){
        sum(p)=k;
        dat(p)=k;
        lm(p)=k;
        rm(p)=k; 
        return;
    }
    int mid=(l(p)+r(p))/2;
    if(x<=mid) change(p*2,x,k);
    if(x>mid) change(p*2+1,x,k);
    sum(p)=sum(p*2)+sum(p*2+1);
    lm(p)=max(lm(p*2),sum(p*2)+lm(p*2+1));
    rm(p)=max(rm(p*2+1),sum(p*2+1)+rm(p*2));
    dat(p)=max(max(lm(p*2),rm(p*2+1)),rm(p*2)+lm(p*2+1));
}
inline node ask(int p,int l,int r){
    if(l<=l(p)&&r>=r(p)) return t[p];
    int mid=(l(p)+r(p))/2;
    if(r<=mid) return ask(p*2,l,r);
    if(l>mid) return ask(p*2+1,l,r);
    node f,r1=ask(p*2,l,mid),r2=ask(p*2+1,mid+1,r);
    f.sum=r1.sum+r2.sum;
    f.lmax=max(r1.lmax,r1.sum+r2.lmax);
    f.rmax=max(r2.rmax,r2.sum+r1.rmax);
    f.dat=max(max(r1.dat,r2.dat),r1.rmax+r2.lmax);
    return f;
}
int main()
{
    n=read(),m=read();
    for(reg int i=1;i<=n;i++) c[i]=read();
    build(1,1,n);
    while(m--){
        int op=read();
        if(op==1){
            int a=read(),b=read();
            if(a>b) swap(a,b);
            printf("%d\n",ask(1,a,b).dat);
        }
        if(op==2){
            int x=read(),k=read();
            change(1,x,k);
        }
    }
    return 0;
}

|