诡异的MLE

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct node{int ans=0,sl=0,sr=0,sum=0;};
int a[N],ans[N*4],sl[N*4],sr[N*4],sum[N*4],n,m;
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
int ps(int x){
    sum[x]=sum[ls(x)]+sum[rs(x)];
    ans[x]=max(ans[ls(x)],ans[rs(x)]);
    ans[x]=max(ans[x],sr[ls(x)]+sl[rs(x)]);
    sl[x]=max(sum[ls(x)]+sl[rs(x)],sl[ls(x)]);
    sr[x]=max(sum[rs(x)]+sr[ls(x)],sr[rs(x)]);
}
void build(int l,int r,int x){
    if(l==r){
        ans[x]=a[l],sl[x]=a[l],sr[x]=a[l];
        sum[x]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(x));
    build(mid+1,r,rs(x));
    ps(x);
}
void f(int l,int r,int x,int w,int k){
    if(l==r){
        a[l]=k;
        ans[x]=sl[x]=sr[x]=a[l];
        sum[x]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    if(w<=mid) f(l,mid,ls(x),w,k);
    else f(mid+1,r,rs(x),w,k);
    ps(x);
}
node hb(node x,node y){
    node c;
    c.sum=x.sum+y.sum;
    c.ans=max(x.ans,y.ans);
    c.ans=max(c.ans,x.sr+y.sl);
    c.sl=max(x.sl,y.sl+x.sum);
    c.sr=max(y.sr,y.sum+x.sr);
    return c;
}
node qs(int l,int r,int x,int ll,int rr){
    node c1,c2;
    bool f1=false,f2=false;
    if(ll<=l&&r<=rr){
        c1.ans=ans[x];
        c1.sl=sl[x];
        c1.sr=sr[x];
        c1.sum=sum[x];
        return c1;
    }
    int mid=(l+r)>>1;
    if(mid>=ll) c1=qs(l,mid,ls(x),ll,rr),f1=true;
    if(mid+1<=rr) c2=qs(mid+1,r,rs(x),ll,rr),f2=true;
    if(f1&&f2) return hb(c1,c2);
    if(f1) return c1;
    if(f2) return c2;   
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,n,1);
    int k;
    while(m--){
        int l,r;node c;
        scanf("%d%d%d",&k,&l,&r);
        if(k==1){
            if(l>r) swap(l,r);
            c=qs(1,n,1,l,r);
            cout<<c.ans<<endl;
        }
        else f(1,n,1,l,r);
    }
    return 0;
}

MLE 改为

int a[N],ans[N*4],sl[N*4],sr[N*4],sum[N*400],n,m;

AC