过一点萌新悲痛求助

P4513 小白逛公园

未知的X @ 2022-11-06 16:50:49

百思不得其解为啥只有9ptsTAT

#include<iostream>
#include<cstdio>
#include<cmath>
#define kl tree[k].l
#define kr tree[k].r
#define mk (kl+kr)>>1
#define lc k<<1
#define rc k<<1|1
#define N 500005
#define klen kr-kl+1
using namespace std;
struct node{
    int l,r,k,sum;
    int lx,rx,px;
};
node tree[N*4];
void build(int k,int l,int r);
void update(int k,int p,int v);
node query(int k,int l,int r);
void down(int k){
    tree[k].lx=max(tree[lc].lx,tree[lc].sum+tree[rc].lx);
    tree[k].rx=max(tree[rc].rx,tree[rc].sum+tree[lc].rx);
    tree[k].sum=tree[lc].sum+tree[rc].sum;
    tree[k].px=max(tree[k].lx,max(tree[k].rx,tree[lc].rx+tree[rc].lx));
}
int n,m;
int main(){
    cin>>n>>m;
    build(1,1,n);
    int op,a,b;
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>a>>b;
            if(a>b) swap(a,b);
            cout<<query(1,a,b).px<<endl;
        }
        if(op==2){
            cin>>a>>b;
            update(1,a,b);
        }
    }
}
void build(int k,int l,int r){
    kl=l;
    kr=r;
    if(l==r){
        cin>>tree[k].sum;
        tree[k].lx=tree[k].rx=tree[k].px=tree[k].sum;
        return;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tree[k].sum=tree[lc].sum+tree[rc].sum;
}
void update(int k,int p,int v){
    if(p<kl||p>kr) return;
    if(kl==kr&&kl==p){
        tree[k].sum=tree[k].lx=tree[k].rx=tree[k].px=v;
        return;
    }
    update(lc,p,v);
    update(rc,p,v);
    down(k);
    return;
}
node query(int k,int l,int r){
    if(tree[k].l>=l&&tree[k].r<=r) return tree[k];
    if(r<=mk) return query(lc,l,r);
    if(l>mk) return query(rc,l,r);
    node t,lt=query(lc,l,r),rt=query(rc,l,r);
    t.lx=max(lt.lx,lt.sum+rt.lx);
    t.rx=max(rt.rx,rt.sum+lt.rx);
    t.sum=lt.sum+rt.sum;
    t.px=max(rt.px,max(lt.px,lt.rx+rt.lx));
    return t;
}

|