萌新刚学线段树，求调代码

Sharing666 @ 2021-04-02 20:09:48

#include <bits/stdc++.h>
using namespace std;

int n,m,ans,score[500002];

struct node{
    int maxl,maxr,sum,l,r,val;
}a[2000002];

void pushup(int num) {
    a[num].maxl=max(a[num*2].maxl,a[num*2].sum+a[num*2+1].maxl);
    a[num].maxr=max(a[num*2+1].maxr,a[num*2+1].sum+a[num*2].maxr);
    a[num].sum=a[num*2].sum+a[num*2+1].sum;
    a[num].val=max(max(a[num*2].val,a[num*2+1].val),a[num*2].maxr+a[num*2+1].maxl);
    a[num].val=max(max(a[num*2].l,a[num*2+1].r),a[num].val);
}

void build(int num,int ll,int rr) {
    a[num].l=ll;
    a[num].r=rr;
    if(ll==rr) {
        a[num].val=a[num].maxl=a[num].maxr=a[num].sum=score[ll];
        return ;
    }
    int mid=(ll+rr)>>1;
    build(num*2,ll,mid);
    build(num*2+1,mid+1,rr);
    pushup(num);
}

void update(int num,int pos,int tmp) {
    if(a[num].l==a[num].r) {
        a[num].val=a[num].maxl=a[num].maxr=a[num].sum=tmp;
        return ;
    }
    if(a[num*2].r>=pos && a[num*2].l<=pos) update(num*2,pos,tmp);
    if(a[num*2+1].r>=pos && a[num*2+1].l<=pos) update(num*2+1,pos,tmp);
    pushup(num);
}

node query(int num,int ll,int rr) {
    if(a[num].l>=ll && a[num].r<=rr) return a[num];
    int mid=(a[num].l+a[num].r)>>1;
    if(rr<=mid) return query(num*2,ll,rr);
    else if(ll>mid) return query(num*2+1,ll,rr);
    else {
        node x;
        node x1=query(num*2,ll,mid),x2=query(num*2+1,mid+1,rr);
        x.maxl=max(x1.maxl,x1.sum+x2.maxl);
        x.maxr=max(x1.maxr+x2.sum,x2.maxr);
        x.sum=x1.sum+x2.sum;
        x.val=max(max(x1.val,x2.val),x1.maxr+x2.maxl);
        return x;
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&score[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++) {
        int k,x,y;
        cin>>k>>x>>y;
        if(k==1) {
            if(x>y) swap(x,y);
            else cout<<query(1,x,y).val<<endl;
        } else update(1,x,y);
    }
    return 0;
}

by slzs @ 2021-04-02 21:17:41

你可以尝试把 子段合并 写成一个函数，想这样：

node qgll(node x,node y) {
    node z;
    z.sum=x.sum+y.sum;
    z.l=max(x.l,x.sum+y.l);
    z.r=max(y.r,y.sum+x.r);
    z.maxn=max(x.r+y.l,max(x.maxn,y.maxn));
    return z;
}

用的时候调用，防止多次打而出错。

by slzs @ 2021-04-02 21:39:46

@Sharing666

struct node{
    int maxl,maxr,sum,l,r,val;
}a[2000002];

改成

struct node{
    int maxl,maxr,sum,val;
}a[2000002];
int ls[2000002],rs[2000002];

亲测以过

by slzs @ 2021-04-02 21:41:26

字打错了， 已

by slzs @ 2021-04-02 21:42:16

可能是调用到了什么奇奇怪怪的东西。 代码：

#include <bits/stdc++.h>
//using namespace std;

int n,m,ans,score[500002];
int max(int x,int y) {return x>y?x:y;}
struct node{
    int maxl,maxr,sum,val;
}a[2000002];
int ls[2000002],rs[2000002];
node qgll(node x,node y) {
    node z;
    z.sum=x.sum+y.sum;
    z.maxl=max(x.maxl,x.sum+y.maxl);
    z.maxr=max(y.maxr,y.sum+x.maxr);
    z.val=max(x.maxr+y.maxl,max(x.val,y.val));
    return z;
}
void pushup(int num) {
    a[num]=qgll(a[num*2],a[num*2+1]);
}

void build(int num,int ll,int rr) {
//  std::swap(num,ll),std::swap(ll,num);
//      printf("%d %d %d\n",num,ll,rr);
    ls[num]=ll,rs[num]=rr;
    if(ll==rr) {
        a[num].val=a[num].maxl=a[num].maxr=a[num].sum=score[ll];
        return ;
    }
    int mid=(ll+rr)>>1;
    build(num*2,ll,mid); build(num*2+1,mid+1,rr);
    pushup(num);
}

void update(int num,int pos,int tmp) {
    if(ls[num]==rs[num]) {
        a[num].val=a[num].maxl=a[num].maxr=a[num].sum=tmp;
        return ;
    }
    if(pos<=rs[num<<1]) update(num*2,pos,tmp);
    else update(num*2+1,pos,tmp);
    pushup(num);
}

node query(int num,int ll,int rr) {
    if(ls[num]>=ll && rs[num]<=rr) return a[num];
    if(rr<=rs[num<<1]) return query(num*2,ll,rr);
    if(ll>=ls[num<<1|1]) return query(num*2+1,ll,rr);
    node x1=query(num*2,ll,rr),x2=query(num*2+1,ll,rr);
    return qgll(x1,x2);
}

signed main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&score[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++) {
        int k,x,y;
        std::cin>>k>>x>>y;
        if(k==1) {
            if(x>y) std::swap(x,y); // why need "else"
            std::cout<<query(1,x,y).val<<std::endl;
        } else update(1,x,y);
    }
    return 0;
}

by Sharing666 @ 2021-04-02 23:13:39

@slzs 已AC，谢谢大神