求助线段树模板题

EDqwq @ 2020-10-27 14:40:27

by EDqwq @ 2020-10-27 14:40:37

#include<bits/stdc++.h>

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct node{
    int l;
    int r;
    int w;
    int ml;
    int mr;
    int sum;
}e[2000010];

int n,m;
int a[500010];

void merge(int i){
    e[i].w = e[i * 2].w + e[i * 2 + 1].w;
    e[i].ml = max(e[i * 2].ml,e[i * 2].w + e[i * 2 + 1].ml);
    e[i].mr = max(e[i * 2 + 1].mr,e[i * 2].mr + e[i * 2 + 1].w);
    e[i].sum = max(max(e[i * 2].sum,e[i * 2 + 1].sum),e[i * 2].mr+e[i * 2 + 1].ml);
}

void build(int i,int l,int r){
    e[i].l = l;
    e[i].r = r;
    if(l == r){
        e[i].w = a[i];
        e[i].ml = e[i].w;
        e[i].mr = e[i].w;
        e[i].sum = e[i].w;
        return ;
    }
    int mid = (l + r) / 2;
    build(i * 2,l,mid);
    build(i * 2 + 1,mid + 1,r);
    merge(i);
}

void update(int i,int l,int w){
    if(e[i].l == e[i].r){
        e[i].ml = w;
        e[i].mr = w;
        e[i].w = w;
        e[i].sum = w;
        return ;
    }
    int mid = (e[i].l + e[i].r) / 2;
    if(l <= mid)update(i * 2,l,w);
    else update(i * 2 + 1,l,w);
    merge(i);
}

node query(int i,int l,int r){
    if(l <= e[i].l && e[i].r <= r)return e[i];
    int mid = (e[i].l + e[i].r) / 2;
    if(r <= mid)return query(i * 2,l,r);
    else {
        if(l > mid)return query(i * 2 + 1,l,r);
        else {
            node s;
            node x,y;
            x = query(i * 2,l,r);
            y = query(i * 2 + 1,l,r);
            s.ml = max(x.ml,x.w + y.ml);
            s.mr = max(y.mr,x.mr + y.w);
            s.sum = max(max(x.sum,y.sum),x.mr + y.ml);
            return s;
        }
    }
}

signed main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i ++)a[i] = read();
    build(1,1,n);
    while(m --){
        int op;
        int l,r;
        op = read(),l = read(),r = read();
        if(op == 1){
            node ans = query(1,l,r);
            cout<<ans.sum<<endl;
        }
        else {
            update(1,l,r);
        }
    }
    return 0;
}

by Kiloio @ 2020-10-27 14:50:59

码风十分友好

by EDqwq @ 2020-10-27 14:55:44

ok事实证明RE是因为空间没开够，但是理论上是够的，可能是因为玄学原因

但是还是WA

by CDFLS_mao_zx @ 2020-10-27 15:21:51

线段树的题一般开4倍够了，RE可以检查一下是不是修改和查询的边界超了1或n，查一下是不是进入了死递归，开大数组当然可以避免RE，但这些原因的WA就不好找了。

by FL4K @ 2020-10-27 15:39:03

码风点名表扬

by ducati @ 2020-10-27 16:51:36

最好开8倍，说不定就行了呢，真的信我一次

by EDqwq @ 2020-10-27 16:52:33

@ducati 哇太强了！！！！！

还是不行（雾

by ducati @ 2020-10-27 16:54:02

@林深时x见鹿 您这个写法太奇怪了

by 云浅知处 @ 2020-10-27 19:50:25

@林深时x见鹿 建树的时候是 e[i].w=a[l] 吧（

感觉可能是因为 a[i] 这里访问的时候越界了 RE？

改了一下这个地方，交上去发现还是 RE/kk，就不懂了

给一下我七月初写的惨不忍睹的代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<iostream>

#define MAXN 500005
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define LL long long

using namespace std;

LL a[MAXN],n,m;

struct Node{

    LL p,q,r,sum;

    Node(LL _p,LL _q,LL _r,LL _s)
        :p(_p),q(_q),r(_r),sum(_s){}
    Node(){}
};

struct SMT{

    Node d[MAXN<<2];

    inline void pushup(LL o){
        d[o].sum=d[lson(o)].sum+d[rson(o)].sum;
        d[o].p=max(max(d[lson(o)].p,d[rson(o)].p),d[lson(o)].r+d[rson(o)].q);
        d[o].q=max(d[lson(o)].q,d[lson(o)].sum+d[rson(o)].q);
        d[o].r=max(d[rson(o)].r,d[rson(o)].sum+d[lson(o)].r);
    }

    inline void build(LL l,LL r,LL o){
        if(l==r){
            d[o]=Node(a[l],a[l],a[l],a[l]);
            return ;
        }
        LL mid=(l+r)>>1;
        build(l,mid,lson(o));
        build(mid+1,r,rson(o));
        pushup(o);
    }

    inline void modify(LL pos,LL k,LL ql,LL qr,LL o){
        if(ql==qr){
            if(ql==pos){
                d[o]=Node(k,k,k,k);
            }
            return ;
        }
        LL mid=(ql+qr)>>1;
        if(pos<=mid)modify(pos,k,ql,mid,lson(o));
        else modify(pos,k,mid+1,qr,rson(o));
        pushup(o);
    }

    inline Node query(LL l,LL r,LL ql,LL qr,LL o){
        if(l<=ql&&qr<=r){
            return d[o];
        }
        LL mid=(ql+qr)>>1;
        Node tmp=Node(-2333333333,-2333333333,-2333333333,-2333333333),t1=Node(-2333333333,-2333333333,-2333333333,-2333333333),t2=Node(-2333333333,-2333333333,-2333333333,-2333333333);
        if(l<=mid){
            t1=query(l,r,ql,mid,lson(o));
        }
        if(r>mid){
            t2=query(l,r,mid+1,qr,rson(o));
        }
        tmp.p=max(max(t1.p,t2.p),t1.r+t2.q);
        tmp.q=max(t1.q,t1.sum+t2.q);
        tmp.r=max(t2.r,t2.sum+t1.r);
        tmp.sum=t1.sum+t2.sum;
        return tmp;
    }

};

SMT tree;

int main(void){

    scanf("%lld%lld",&n,&m);

    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }

    tree.build(1,n,1);

    while(m--){
        LL opt,l,r;
        scanf("%lld%lld%lld",&opt,&l,&r);
        if(opt==1){
            if(l>=r){
                swap(l,r);
            }
            printf("%lld\n",tree.query(l,r,1,n,1).p);
        }
        else{
            tree.modify(l,r,1,n,1);
        }
    }

    return 0;
}

by EDqwq @ 2020-10-27 19:51:15

@云浅知处 谢谢泥w，但是另一位神犇已经帮窝改了还安利了三倍经验

但是还是谢谢泥/qq/qq/qq