线段树模板，单点修改+区间最大子段和，9pts,只AC第一个点

P4513 小白逛公园

dxy2020 @ 2022-10-04 21:11:55

#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].sum=Tree[u<<1].sum+Tree[u<<1|1].sum;
    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].dat=max (Tree[u<<1].rdat+Tree[u<<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<L) return query (L,R,mid+1,r,u<<1|1);
    if (mid>=R) return query (L,R,l,mid,u<<1);
    Segment_Tree ll,rr,Dat;
    ll=query (L,mid,l,mid,u<<1);
    rr=query (mid+1,R,mid+1,r,u<<1|1);
    Dat.sum=ll.sum+rr.sum;
    Dat.ldat=max (ll.ldat,ll.sum+rr.ldat);
    Dat.rdat=max (rr.rdat,rr.sum+ll.rdat);
    Dat.dat=max (ll.rdat+rr.ldat,max (ll.ldat,rr.rdat));
    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 Aishiteru_zwy @ 2022-10-04 21:17:32

#include "cstdio"
using namespace std;
void read (int &a){
    int k=1;a=0;
    char c=getchar();
    while (c<48||c>57){if (c=='-') k=-1;c=getchar();}
    while (c>=48&&c<=57){a=a*10+c-'0';c=getchar();}
    a*=k;
}

int max (int x,int y){
    return x>y?x:y;
}

struct tree{
    int lm,rm,maxx,s;
}tr[2000005];

void pushup (int u){
    tr[u].lm=max(tr[u<<1].lm,tr[u<<1].s+tr[u<<1|1].lm);
    tr[u].rm=max(tr[u<<1|1].rm,tr[u<<1|1].s+tr[u<<1].rm);
    tr[u].s=tr[u<<1].s+tr[u<<1|1].s;
    tr[u].maxx=max(tr[u<<1].maxx,max(tr[u<<1|1].maxx,tr[u<<1].rm+tr[u<<1|1].lm));
}

void build (int l,int r,int u){
    if (l==r){
        read(tr[u].s);
        tr[u].lm=tr[u].rm=tr[u].maxx=tr[u].s;
        return;
    }
    int m=l+r>>1;
    build(l,m,u<<1);build(m+1,r,u<<1|1);
    pushup(u);
}

void update (int L,int x,int l,int r,int u){
    if (l==r){
        tr[u].s=x;
        tr[u].lm=tr[u].rm=tr[u].maxx=tr[u].s;
        return;
    }
    int m=l+r>>1;
    if (L<=m) update(L,x,l,m,u<<1);
    else update(L,x,m+1,r,u<<1|1);
    pushup(u);
}

tree query (int L,int R,int l,int r,int u){
    if (L<=l&&r<=R) return tr[u];
    int m=l+r>>1;
    tree ans,ls,rs;
    if (R<=m) return query(L,R,l,m,u<<1);
    else if (L>m) return query(L,R,m+1,r,u<<1|1);
    else{
        ls=query(L,R,l,m,u<<1);
        rs=query(L,R,m+1,r,u<<1|1);
        ans.lm=max(ls.lm,ls.s+rs.lm);
        ans.rm=max(rs.rm,rs.s+ls.rm);
        ans.s=ls.s+rs.s;
        ans.maxx=max(ls.maxx,max(rs.maxx,ls.rm+rs.lm));
        return ans;
    }
}

int main (){
    int n,m,k,a,b;
    read(n);read(m);
    build(1,n,1);
    for (int i=1;i<=m;i++){
        read(k);read(a);read(b);
        if (k==1){
            if (a>b){
                a+=b;
                b=a-b;
                a=a-b;
            }
            printf ("%d\n",query(a,b,1,n,1).maxx);
        }
        else update(a,b,1,n,1);
    }
    return 0;
}

by Iamzzr @ 2022-10-04 21:19:00

@dxy2020

测试数据可能会出现 a>b 的情况，需要进行交换

by Iamzzr @ 2022-10-04 21:20:12

《当我看完了你繁杂的 pushup 之后感觉没问题苦苦思索无果然后又看了一眼题这件逝》

by dxy2020 @ 2022-10-04 21:25:07

@Iamzzr 我交换了啊？？

by bamboo12345 @ 2022-10-04 21:27:10

@dxy2020 query的问题

by Iamzzr @ 2022-10-04 21:27:56

@dxy2020 不好意思我是傻逼。

这两句错了：

    ll=query (L,mid,l,mid,u<<1);
    rr=query (mid+1,R,mid+1,r,u<<1|1);

by dxy2020 @ 2022-10-04 21:29:17

@Iamzzr 我改了，无果

by Iamzzr @ 2022-10-04 21:33:54

hack：

5 1
1 4 -3 4 5
1 2 4

by dxy2020 @ 2022-10-04 21:38:15

@Iamzzr 不是5吗？？

by Iamzzr @ 2022-10-04 21:46:21

@dxy2020 这组试试看？

| 下一页