TsH_GD @ 2022-11-26 08:18:13

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=5e5+10;

int n,m;
int a[maxn];

struct segment_tree{
    struct Node{
        int l,r;
        int sum;
        int maxsum;
        int lsum,rsum;
    }tr[maxn*4];

    void build(int p,int l,int r){
        tr[p]={l,r,-100000,-100000,-100000,-100000};
        if(l==r){
            tr[p].sum=tr[p].lsum=tr[p].rsum=tr[p].maxsum=a[l];
            return ;
        }

        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
        tr[p].lsum=max(tr[p<<1].lsum,tr[p<<1|1].lsum+tr[p<<1].sum);
        tr[p].rsum=max(tr[p<<1|1].rsum,tr[p<<1].rsum+tr[p<<1|1].sum);
        tr[p].maxsum=max(tr[p<<1].maxsum,max(tr[p<<1|1].maxsum,tr[p<<1].rsum+tr[p<<1|1].lsum));
    }

    void change(int p,int x,int k){
        if(tr[p].l>x||tr[p].r<x) return ;
        if(tr[p].l==x&&tr[p].r==x){
            tr[p].sum=tr[p].lsum=tr[p].maxsum=tr[p].rsum=k;
            return ;
        }
        change(p<<1,x,k);
        change(p<<1|1,x,k);
        tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
        tr[p].lsum=max(tr[p<<1].lsum,tr[p<<1|1].lsum+tr[p<<1].sum);
        tr[p].rsum=max(tr[p<<1|1].rsum,tr[p<<1].rsum+tr[p<<1|1].sum);
        tr[p].maxsum=max(tr[p<<1].maxsum,max(tr[p<<1|1].maxsum,tr[p<<1].rsum+tr[p<<1|1].lsum));
    }

    int check(int p,int l,int r){
        if(tr[p].l>r||tr[p].r<l) return -100000;
        if(tr[p].l>=l&&tr[p].r<=r)  return tr[p].maxsum;
        int s=-100000;
        s=max(s,check(p<<1,l,r));
        s=max(s,check(p<<1|1,l,r));
        return s;
    }
}ST;

signed main(){
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    ST.build(1,1,n);

    for(int i=1;i<=m;i++){
        int op,x,y;
        scanf("%lld %lld %lld",&op,&x,&y);
        if(op&1){
            if(x>y) swap(x,y);
            printf("%lld\n",ST.check(1,x,y));
        }
        else{
            ST.change(1,x,y);
        }
    }
}

by dxy2020 @ 2022-11-26 08:32:19

#include <bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
inline void in (int &x){
    int f=1;x=0;char c=getchar();
    while (c>'9'||c<'0'){if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
    x*=f;
}
int n,q,op,x,y,a[N];
struct Segment_Tree{
    int sum,ldat,rdat,dat;
}Tree[N<<2];
inline void push_up (int u){
    Tree[u].ldat=max (Tree[u<<1].ldat,Tree[u<<1].sum+Tree[u<<1|1].ldat);
    Tree[u].rdat=max (Tree[u<<1|1].rdat,Tree[u<<1|1].sum+Tree[u<<1].rdat);
    Tree[u].sum=Tree[u<<1].sum+Tree[u<<1|1].sum;
    Tree[u].dat=max (Tree[u<<1].rdat+Tree[u<<1|1].ldat,max (Tree[u<<1].dat,Tree[u<<1|1].dat));
}
inline void build (int l,int r,int u){
    if (l==r){Tree[u].sum=Tree[u].ldat=Tree[u].rdat=Tree[u].dat=a[l];return ;}
    int mid=l+r>>1;
    build (l,mid,u<<1);build (mid+1,r,u<<1|1);
    push_up (u);
}
inline void update (int x,int y,int l,int r,int u){
    if (l==r){Tree[u].dat=Tree[u].ldat=Tree[u].rdat=Tree[u].sum=y;return ;}
    int mid=l+r>>1;
    if (x<=mid) update (x,y,l,mid,u<<1);
    if (x>mid) update (x,y,mid+1,r,u<<1|1);
    push_up (u);
}
inline Segment_Tree query (int L,int R,int l,int r,int u){
    if (L<=l&&R>=r) return Tree[u];
    int mid=l+r>>1;
    if (mid>=R) return query (L,R,l,mid,u<<1);
    else if (mid<L) return query (L,R,mid+1,r,u<<1|1);
    else{
        Segment_Tree ll,rr,Dat;
        ll=query (L,R,l,mid,u<<1);
        rr=query (L,R,mid+1,r,u<<1|1);
        Dat.ldat=max (ll.ldat,ll.sum+rr.ldat);
        Dat.rdat=max (rr.rdat,rr.sum+ll.rdat);
        Dat.sum=ll.sum+rr.sum;
        Dat.dat=max (ll.rdat+rr.ldat,max (ll.dat,rr.dat));
        return Dat;
    }
}
signed main (){
    in (n);in (q);
    for (int i=1;i<=n;++i) in (a[i]);
    build (1,n,1);
    for (int i=1;i<=q;++i){
        in (op);in (x);in (y);
        if (op==1){if (x>y) swap (x,y);printf ("%lld\n",query (x,y,1,n,1).dat);}
        else update (x,y,1,n,1);
    }
    return 0;
}

给你做个参考。

by chlchl @ 2022-11-26 09:16:31

@God_Dream 您这样写有问题，check 左右儿子合并之后左儿子右端点和右儿子左端点加起来的那部分您似乎没有判断。

楼上的代码可以参考一下。

by TsH_GD @ 2022-11-26 09:25:34

@caihaolang 不太理解，咋改啊

by chlchl @ 2022-11-26 11:03:13

@God_Dream

s=max(s,check(p<<1,l,r));
s=max(s,check(p<<1|1,l,r));

这里您只是比较了左右儿子的最大子段和，事实上它们合并成一个区间以后，您还需要比较它们拼起来后中间的那段和，即 tr[p<<1].rsum+tr[p<<1|1].lsum 的这部分，您的 check 函数并没有比较。

改法就是，check 返回一个结构体。类似这样：

node query(int o, int l, int r, int s, int t){
    if(l >= s && r <= t)
        return (node){ans[o], lm[o], rm[o], sum[o]};
    int mid = (l + r) >> 1;
    node now = (node){0, 0, 0, 0};
    if(t <= mid)
        return query(ls(o), l, mid, s, t);
    if(s > mid)
        return query(rs(o), mid + 1, r, s, t);
    node p = query(ls(o), l, mid, s, t);
    node q = query(rs(o), mid + 1, r, s, t);
    now.sum = p.sum + q.sum;
    now.lres = max(p.lres, p.sum + q.lres);
    now.rres = max(q.rres, q.sum + p.rres);
    now.res = max(max(p.res, q.res), p.rres + q.lres);
    return now;
}

by TsH_GD @ 2022-11-27 09:21:49

@caihaolang 看是看懂了，额。。我这个代码咋改啊。。不会了

by chlchl @ 2022-11-27 11:04:01

@God_Dream 把 check 的返回值类型改成 segment\_tree，把它的返回值当成一个节点看待，很容易能写出来。