线段树9分求调，马蜂好看，思路清晰

m1kusama @ 2024-02-27 21:35:03

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
struct tree{
    int l,r,ma,sum,lma,rma;

    tree(){
        sum=0;
        ma=lma=rma=-999999999;
        l=-1;
    } 
}t[N<<2];

void debug(){
    for(int i=1;i<(N<<2);i++){
        if(t[i].l!=-1){
            cout<<i<<" "<<t[i].l<<" "<<t[i].r<<" lma:"<<t[i].lma<<" rma:"<<t[i].rma<<" ma:"<<t[i].ma<<" sum:"<<t[i].sum<<"\n";
        }
    }
}
int a[N],n,m,x,y,k,opt;
void pushup(int now){
    t[now].sum=t[now<<1].sum+t[now<<1|1].sum;
    t[now].lma=max(t[now<<1].lma,t[now<<1].sum+t[now<<1|1].lma);
    t[now].rma=max(t[now<<1|1].rma,t[now<<1|1].sum+t[now<<1].rma);
    t[now].ma=max(t[now<<1].rma+t[now<<1|1].lma,max(t[now<<1].ma,t[now<<1|1].ma));
    //t[now].ma=max(t[now].ma,max(t[now].lma,t[now].rma));
}
void build(int now,int l,int r){
    t[now].l=l,t[now].r=r;
    if(l==r) return t[now].sum=t[now].lma=t[now].rma=t[now].ma=a[l],void();
    int mid=(l+r)>>1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    pushup(now);
}
tree ask(int now,int l,int r){
    tree ans;
    if(l<=t[now].l&&t[now].r<=r){
        return t[now];
    }
    int mid=(t[now].l+t[now].r)>>1;
    if(r<=mid) return ask(now<<1,l,r);
    else if(l>mid) return ask(now<<1|1,l,r);
    else{
        tree a=ask(now<<1,l,t[now<<1].r),b=ask(now<<1|1,t[now<<1|1].l,r);
        ans.l=a.l,ans.r=b.r;
        ans.sum=a.sum+b.sum;
        ans.lma=max(a.sum+b.lma,ans.ma);
        ans.rma=max(b.sum+a.rma,ans.ma);
        ans.ma=max(a.ma,max(b.ma,a.rma+b.lma));
        return ans;
    }
}
void update(int now,int pos,int k){
    if(t[now].l==t[now].r and t[now].l==pos)
        return t[now].sum=t[now].lma=t[now].rma=t[now].ma=k,void();
    int mid=(t[now].l+t[now].r)>>1;
    if(pos<=mid)update(now<<1,pos,k);
    else update(now<<1|1,pos,k);
    pushup(now);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(m--){
        cin>>opt>>x>>y;
        if(opt==1){
            if(x>y)swap(x,y);
            tree ans=ask(1,x,y);
            cout<<ans.ma<<endl;
        }
        else update(1,x,y);
    }
    return 0;
}

by LiJoQiao @ 2024-02-27 22:02:19

ask 里面 if(l<=t[now].l&&t[now].r<=r)。

by LiJoQiao @ 2024-02-27 22:03:59

        ans.lma=max(a.sum+b.lma,ans.ma);
        ans.rma=max(b.sum+a.rma,ans.ma);

by chroneZ @ 2024-02-27 22:05:32

有没有可能是

ans.lma=max(a.sum+b.lma,a.lma);
ans.rma=max(b.sum+a.rma,b.rma);

by myyyIisq2R @ 2024-02-28 14:34:01

提供马蜂不好看，思路不清晰的线段树

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+1;
int a[N];
int qzh[N]; 
int b[N];
struct Tree
{
    #define lson(x) x<<1
    #define rson(x) x<<1|1
    struct node
    {
        int l,r,val,lz;
        int lmax,rmax;
        int max;

    }tree[N<<2];
    void pushup(int x)
    {
        tree[x].val = tree[lson(x)].val + tree[rson(x)].val;
        tree[x].lmax = max(tree[lson(x)].lmax,tree[lson(x)].val + tree[rson(x)].lmax);
        tree[x].rmax = max(tree[rson(x)].rmax,tree[rson(x)].val + tree[lson(x)].rmax);
        tree[x].max = max(max(tree[lson(x)].max,tree[rson(x)].max),tree[lson(x)].rmax+tree[rson(x)].lmax);
        return;
    }
    void build(int l,int r,int x)
    {
        tree[x].l = l;
        tree[x].r = r;
        if(l == r)
        {
            tree[x].val = a[l];
            tree[x].lmax = a[l];
            tree[x].rmax = a[l];
            tree[x].max = a[l];
            return;
        }
        int mid = l+r>>1;
        build(l,mid,lson(x));
        build(mid+1,r,rson(x));
        pushup(x);
    }
    void pushdown(int x)
    {
        if(tree[x].lz)
        {
            tree[lson(x)].lz += tree[x].lz;
            tree[rson(x)].lz += tree[x].lz;
            int mid = tree[x].l + tree[x].r >> 1;
            tree[lson(x)].val += tree[x].lz * (mid-tree[x].l+1);
            tree[rson(x)].val += tree[x].lz * (tree[x].r-mid);
            tree[x].lz &= 0;
        }
    }
    void update(int l,int r,int k,int x)
    {
        if(tree[x].l == l&&tree[x].r == r)
        {
            tree[x].max = tree[x].lmax = tree[x].rmax = tree[x].val = k;
            return;
        }
        pushdown(x);
        int mid = tree[x].l + tree[x].r >> 1;

        if(l>mid) update(l,r,k,rson(x));
        else update(l,r,k,lson(x));
        pushup(x);
    }
    int query(int l,int r,int x)
    {
        if(l<=tree[x].l && tree[x].r <= r)
        {
            return tree[x].val;
        }
        pushdown(x);
        int mid = tree[x].l + tree[x].r >> 1;
        int ans{};
        if(l<=mid) ans+=query(l,r,lson(x));
        if(r>mid) ans+=query(l,r,rson(x));
        return ans;
    }
    node query2(int l,int r,int x)
    {
        if(l<=tree[x].l && tree[x].r <= r)
        {
            return tree[x];
        }
        pushdown(x);
        int mid = tree[x].l + tree[x].r >> 1;
        if(mid<l)return query2(l,r,rson(x));
        else if(mid>=r) return query2(l,r,lson(x));
        else
        {
            node a,b;
            a = query2(l,r,lson(x));
            b = query2(l,r,rson(x));
            node t;
            t.max = max(max(a.max,b.max),a.rmax+b.lmax);
            t.lmax = max(a.lmax,a.val+b.lmax);
            t.rmax = max(b.rmax,a.rmax+b.val);
            return t;
        }

    }
}tree[2];

signed main()
{
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);

    #endif

        int n,m;
        cin>>n>>m;
    for(int i{1};i<=n;i++)
    {
        cin>>a[i];
    }
    tree[1].build(1,n,1);
    while(m--)
    {
        int k;
        cin>>k;
        int l,r;
        cin>>l>>r;
        if(k == 1)
        {
            if(l>r) swap(l,r);
            cout<<tree[1].query2(l,r,1).max<<endl;
        }
        else
        {
            tree[1].update(l,l,r,1);
        }
    }

}//13
//1 2 1 1  2 1 0