18pts 求助

P4513 小白逛公园

hundunqidian @ 2022-10-03 09:47:17

过了前两个点,其余点RE


using namespace std;
int const X=1e6+10;
int n,m,a[X],k,aa,bb;
struct tree{
    int LS,RS,sum,S;
};
tree t[X<<2];
inline int ls(int x){
    return x<<2;
}
inline int rs(int x){
    return x<<2 | 1;
}
void pushup(tree &rt,tree &tL,tree &tR){
    rt.S=max(tL.RS+tR.LS,max(tL.S,tR.S));
    rt.LS=max(tL.LS,tL.sum+tR.LS);
    rt.RS=max(tR.RS,tL.RS+tR.sum);
    rt.sum=tL.sum+tR.sum;
    return ;
}
void build(int rt,int L,int R){
    if(L==R){
        t[rt].S=a[L];
        t[rt].LS=a[L];
        t[rt].RS=a[L];
        t[rt].sum=a[L];
        return ;
    }
    int mid=(L+R)>>1;
    build(ls(rt),L,mid);
    build(rs(rt),mid+1,R);
    pushup(t[rt],t[ls(rt)],t[rs(rt)]);
    return ;
}
tree query(int rt,int L,int R,int qL,int qR){
    if(qL<=L && R<=qR){
        return t[rt];
    }
    int mid=(L+R)>>1;
    if(qL<=mid && mid+1<=qR){
        tree res,A,B;
        A=query(ls(rt),L,mid,qL,qR);
        B=query(rs(rt),mid+1,R,qL,qR);
        pushup(res,A,B);
        return res;
    }
    else if(qL<=mid){
        return query(ls(rt),L,mid,qL,qR);
    }
    else{
        return query(rs(rt),mid+1,R,qL,qR);
    }
}
void change(int rt,int L,int R,int p,int s){
    if(L==R){
        t[rt].sum=s;
        t[rt].LS=s;
        t[rt].RS=s;
        t[rt].S=s;
        return ;
    }
    int mid=(L+R)>>1;
    if(mid>=p){
        change(ls(rt),L,mid,p,s);
    }
    else{
        change(rs(rt),mid+1,R,p,s);
    }
    pushup(t[rt],t[ls(rt)],t[rs(rt)]);
    return ;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        cin>>k>>aa>>bb;
        if(k==1){
            if(aa>bb) swap(aa,bb);
            cout<<query(1,1,n,aa,bb).S<<endl;
        }
        else{
            change(1,1,n,aa,bb);
        }
    }
    return 0;
} ```

by wangyubin1qaz @ 2022-10-03 10:11:29

你的头文件呢? (萌新回复)


by hundunqidian @ 2022-10-03 10:57:17

@wangyubin1qaz ……可能没复制上

 #include<bits/stdc++.h>//(补)

by wangyubin1qaz @ 2022-10-03 11:06:58

@hundunqidian 。。。


by wangyubin1qaz @ 2022-10-03 11:07:55

我再看一下


by hundunqidian @ 2022-10-04 16:07:46

@wangyubin1qaz 谢谢,已经查出错了 (ls和rs多左移了一位)


|