萌新刚学线段树$10^{-9}s$，求助

P4513 小白逛公园

S0CRiA @ 2021-05-02 17:46:32

//P4513
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn=500010;
int a[maxn];
struct SegmentTree{
    struct node{
        int sum,lm,rm,am;
    } t[maxn<<2];
    inline void update(int n){
        t[n].sum=t[n<<1].sum+t[n<<1|1].sum;
        t[n].lm=t[n<<1].lm;
        t[n].rm=t[n<<1|1].rm;
        t[n].am=max(max(t[n].lm,t[n].rm),t[n<<1].rm+t[n<<1|1].lm);
        return;
    }
    inline void buildtree(int l,int r,int n){
        if(l==r){
            t[n].sum=t[n].lm=t[n].rm=t[n].am=a[l];
            return;
        }
        int mid=l+r>>1;
        buildtree(l,mid,n<<1),buildtree(mid+1,r,n<<1|1),update(n);
        return;
    }
    inline void modify(int l,int r,int n,int k,int val){
        if(l==r){
            t[n].sum=t[n].lm=t[n].rm=t[n].am=val;
            return;
        }
        int mid=l+r>>1;
        if(k<=mid) modify(l,mid,n<<1,k,val);
        else modify(mid+1,r,n<<1|1,k,val);
        update(n);
        return;
    }
    inline node ask(int l,int r,int n,int ll,int rr){
        if(ll<=l&&r<=rr) return t[n];
        int mid=l+r>>1;
        if(rr<=mid) return ask(l,mid,n<<1,ll,rr);
        if(ll>mid) return ask(mid+1,r,n<<1|1,ll,rr);
        node x=ask(l,mid,n<<1,ll,rr),y=ask(mid+1,r,n<<1|1,ll,rr),res;
        res.sum=x.sum+y.sum;
        res.lm=max(x.lm,x.sum+y.lm);
        res.rm=max(y.rm,x.rm+y.sum);
        res.am=max(max(x.am,y.am),x.rm+y.lm);
        return res;
    }
} T;

int main(){
    int n,m,k,A,b;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i)
        scanf("%d",&a[i]);
    T.buildtree(1,n,1);
    for(int i=1; i<=m; ++i){
        scanf("%d%d%d",&k,&A,&b);
        switch(k){
            case 1:
                if(A>b) swap(A,b);
                printf("%d\n",T.ask(1,n,1,A,b).am);
                break;
            case 2:
                T.modify(1,n,1,A,b);
                break;
        }
    }
    return 0;
}

样例是过的，但只得了九分

by fjy666 @ 2021-05-02 18:02:50

@Fее_cle6418 对不起，看错了。
您的线段树并没有保存 l,r
谢罪谢罪orz

by S0CRiA @ 2021-05-02 18:03:38

应该是modify的问题

by S0CRiA @ 2021-05-02 18:05:26

@fjy666 但是我的线段树一直是这么写的qwq

一边递归一边算l,r

by Saliеri @ 2021-05-02 18:08:58

@Fее_cle6418 pushup 里面 lm 和 rm 的更新需要讨论吧：比如 lm 还需要讨论跨越整个左区间之后接到右区间的情况。

by S0CRiA @ 2021-05-02 18:14:16

@shangcheng 改了还是错

    inline void update(int n){
        t[n].sum=t[n<<1].sum+t[n<<1|1].sum;
        t[n].lm=max(t[n<<1].lm,t[n<<1].sum+t[n<<1|1].lm);
        t[n].rm=max(t[n<<1|1].rm,t[n<<1].lm+t[n<<1|1].sum);
        t[n].am=max(max(t[n].lm,t[n].rm),t[n<<1].rm+t[n<<1|1].lm);
        return;
    }

by S0CRiA @ 2021-05-02 18:15:17

啊第三行应该是t[n<<1].rm

by S0CRiA @ 2021-05-03 08:30:12

OHHHHHHHH

过了

是update的问题

inline void update(int n){
        t[n].sum=t[n<<1].sum+t[n<<1|1].sum;
        t[n].lm=max(t[n<<1].lm,t[n<<1].sum+t[n<<1|1].lm);
        t[n].rm=max(t[n<<1|1].rm,t[n<<1].rm+t[n<<1|1].sum);
        t[n].am=max(max(t[n<<1].am,t[n<<1|1].am),t[n<<1].rm+t[n<<1|1].lm);
        return;
    }