蒟蒻萌新过不了编译qwq

Infinity_Fantasy @ 2024-02-10 22:55:33

#include<bits/stdc++.h>
using namespace std;
int n,m,op,x,y;
struct node{
    int maxv,maxl,maxr,sum;
}tmp,tree[1000005];
void pushup(node &fa,node &ls,node &rs){
    if(ls.maxr<0&&rs.maxl<0) fa.maxv=max(ls.maxr,rs.maxl);
    else{
        fa.maxv=0;
        if(ls.maxr>0) fa.maxv+=ls.maxr;
        if(rs.maxl>0) fa.maxv+=rs.maxl;
    }
    fa.maxv=max(max(fa.maxv,ls.maxr),rs.maxl);
    fa.maxl=max(ls.maxl,ls.sum+rs.maxl);
    fa.maxr=max(rs.maxr,rs.sum+ls.maxr);
    fa.sum=ls.sum+rs.sum;
}
void build(int p,int l,int r){
    if(l==r){
        cin>>tree[p].maxv;
        tree[p].sum=tree[p].maxl=tree[p].maxr=tree[p].maxv;
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(tree[p],tree[p<<1],tree[p<<1|1]);
}
void update(int p,int l,int r,int k,int d){
    if(l==r){
        tree[p].maxl=tree[p].maxr=tree[p].maxv=tree[p].sum=d;
        return;
    }
    int mid=l+r>>1;
    if(k<mid) update(p<<1,l,mid,k,d);
    else update(p<<1|1,mid+1,r,k,d);
    pushup(tree[p],tree[p<<1],tree[p<<1|1]);
}
node query(int p,int l,int r,int s,int c){
    if(s<=l&&r<=c) return tree[p];
    int mid=l+r>>1;
    if(s<=mid&&mid<=c){
        tmp.maxl=tmp.maxr=tmp.maxv=tmp.sum=0;
        pushup(tmp,query(p<<1,l,mid,s,c),query(p<<1|1,mid+1,r,s,c));
        return tmp;
    }else if(s<=mid) return query(p<<1,l,mid,s,c);
    return query(p<<1|1,mid+1,r,s,c);
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    build(1,1,n);
    while(m--){
        cin>>op>>x>>y;
        if(op==1){
            if(x>y) swap(x,y);
            cout<<query(1,1,n,x,y).maxv<<"\n";
        }else update(1,1,n,x,y);
    }
    return 0;
}

by 杜都督 @ 2024-02-10 23:59:19

@Infinity_Fantasy 看一下私信，我感觉要重写了

by 杜都督 @ 2024-02-11 01:04:53

改A了，有好多小细节

#include<bits/stdc++.h>
using namespace std;
int n,m,op,x,y;
struct node{
    int maxv,maxl,maxr,sum;
}tmp,tree[2000005];
void pushup(node &fa,const node &ls,const node &rs){
    if(ls.maxr<0&&rs.maxl<0) fa.maxv=max(ls.maxr,rs.maxl);
    else{
        fa.maxv=0;
        if(ls.maxr>0) fa.maxv+=ls.maxr;
        if(rs.maxl>0) fa.maxv+=rs.maxl;
    }
    fa.maxv=max(max(fa.maxv,ls.maxv),rs.maxv);
    fa.maxl=max(ls.maxl,ls.sum+rs.maxl);
    fa.maxr=max(rs.maxr,rs.sum+ls.maxr);
    fa.sum=ls.sum+rs.sum;
}
void build(int p,int l,int r){
    if(l==r){
        cin>>tree[p].maxv;
        tree[p].sum=tree[p].maxl=tree[p].maxr=tree[p].maxv;
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(tree[p],tree[p<<1],tree[p<<1|1]);
}
void update(int p,int l,int r,int k,int d){
    if(l==r){
        tree[p].maxl=tree[p].maxr=tree[p].maxv=tree[p].sum=d;
        return;
    }
    int mid=l+r>>1;
    if(k<=mid) update(p<<1,l,mid,k,d);
    else update(p<<1|1,mid+1,r,k,d);
    pushup(tree[p],tree[p<<1],tree[p<<1|1]);
}
node query(int p,int l,int r,int s,int c){
    if(s<=l&&r<=c) return tree[p];
    int mid=l+r>>1;
    if(s<=mid&&mid<c){
        tmp.maxl=tmp.maxr=tmp.maxv=tmp.sum=0;
        pushup(tmp,query(p<<1,l,mid,s,c),query(p<<1|1,mid+1,r,s,c));
        return tmp;
    }else if(s<=mid) return query(p<<1,l,mid,s,c);
    return query(p<<1|1,mid+1,r,s,c);
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    build(1,1,n);
    while(m--){
        cin>>op>>x>>y;
        if(op==1){
            if(x>y) swap(x,y);
            cout<<query(1,1,n,x,y).maxv<<"\n";
        }else update(1,1,n,x,y);
    }
    return 0;
}

by 杜都督 @ 2024-02-11 01:11:27

1. tree[]要开4*n空间

2. pushup()中后两个形参加上const修饰，还有

fa.maxv=max(max(fa.maxv,ls.maxv),rs.maxv);

3. update()中

if(k<=mid)

4. query()中

if(s<=mid&&mid<c)