9pts求调，玄关

cbkxx @ 2024-02-27 22:36:47

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
int n,m,a[500005]; 
struct node{
    int s1,s2,s3,s4;
}t[2000005];
void push_up(int x){
    t[x].s1=t[x*2].s1+t[x*2+1].s1;
    t[x].s2=max(t[x*2].s2,t[x*2].s1+t[x*2+1].s2);
    t[x].s3=max(t[x*2+1].s3,t[x*2+1].s1+t[x*2].s3);
    t[x].s4=max(max(t[x*2].s4,t[x*2+1].s4),t[x*2].s2+t[x*2+1].s3);
} 
void build(int l,int r,int x){
    if(l==r){
        t[x].s1=t[x].s2=t[x].s3=t[x].s4=a[l];
        return;
    }
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    push_up(x);
}
node ask(int L,int R,int l,int r,int x){
    if(l>=L&&r<=R)return t[x];
    if(R<=mid)return ask(L,R,l,mid,x*2);
    if(L>mid)return ask(L,R,mid+1,r,x*2+1);
    node ans,a1=ask(L,R,l,mid,x*2),b1=ask(L,R,mid+1,r,x*2+1);
    ans.s1=a1.s1+b1.s1;
    ans.s2=max(a1.s2,a1.s1+b1.s2);
    ans.s3=max(b1.s3,b1.s1+a1.s3);
    ans.s4=max(max(a1.s4,b1.s4),a1.s2+b1.s3);
    return ans;
}
void add(int d,int e,int l,int r,int x){
    if(l==r){
        t[x].s1=t[x].s2=t[x].s3=t[x].s4=e;
        return;
    }
    if(d<=mid)add(d,e,l,mid,x*2);
    else add(d,e,mid+1,r,x*2+1); 
    push_up(x);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    build(1,n,1);
    while(m--){
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1){
            if(x>y)swap(x,y);
            printf("%d\n",ask(x,y,1,n,1).s4);
        }else{
            add(x,y,1,n,1);
        }
    }
    return 0;
}

by cbkxx @ 2024-02-27 22:37:55

注:本人还要上学，可能无法及时看到回复

by _XHY20180718_ @ 2024-02-28 07:41:45

@cbkxx 改完了，死因：pushup最后一句应该是左儿子包含右端点的最大子段和+右儿子包含左端点的最大子段和。

100pts代码：

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
int n,m,a[500005]; 
struct node{
    int s1,s2,s3,s4;
}t[2000005];
void push_up(int x){
    t[x].s1=t[x*2].s1+t[x*2+1].s1;
    t[x].s2=max(t[x*2].s2,t[x*2].s1+t[x*2+1].s2);
    t[x].s3=max(t[x*2+1].s3,t[x*2+1].s1+t[x*2].s3);
    t[x].s4=max(max(t[x*2].s4,t[x*2+1].s4),t[x*2].s3+t[x*2+1].s2);
} 
void build(int l,int r,int x){
    if(l==r){
        t[x].s1=t[x].s2=t[x].s3=t[x].s4=a[l];
        return;
    }
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    push_up(x);
}
node ask(int L,int R,int l,int r,int x){
    if(l>=L&&r<=R)return t[x];
    if(R<=mid)return ask(L,R,l,mid,x*2);
    if(L>mid)return ask(L,R,mid+1,r,x*2+1);
    node ans,a1=ask(L,R,l,mid,x*2),b1=ask(L,R,mid+1,r,x*2+1);
    ans.s1=a1.s1+b1.s1;
    ans.s2=max(a1.s2,a1.s1+b1.s2);
    ans.s3=max(b1.s3,b1.s1+a1.s3);
    ans.s4=max(max(a1.s4,b1.s4),a1.s3+b1.s2);
    return ans;
}
void add(int d,int e,int l,int r,int x){
    if(l==r){
        t[x].s1=t[x].s2=t[x].s3=t[x].s4=e;
        return;
    }
    if(d<=mid)add(d,e,l,mid,x*2);
    else add(d,e,mid+1,r,x*2+1); 
    push_up(x);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    build(1,n,1);
    while(m--){
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1){
            if(x>y)swap(x,y);
            printf("%d\n",ask(x,y,1,n,1).s4);
        }else{
            add(x,y,1,n,1);
        }
    }
    return 0;
}

by cbkxx @ 2024-02-28 16:17:29

@XHY20180718 谢谢，已关