萌新刚学OI，9pts求调

lutaoquan2012 @ 2024-05-22 19:06:14

//
// Created by 55062 on 2024/5/22.
//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,a[500010];
struct node{
    ll l,r,sum,lnum,rnum,num;
}t[1000100];
void pushup(ll x){
    t[x].sum=t[x].sum+t[x].sum;
    t[x].lnum=max(t[x*2].lnum,t[x*2].sum+t[x*2+1].lnum);    
    t[x].rnum=max(t[x*2+1].rnum,t[x*2+1].sum+t[x*2].rnum);
    t[x].num=max({t[x].lnum,t[x].rnum,t[x*2].rnum+t[x*2+1].lnum});
}
void build(ll x,ll l,ll r){
    t[x].l=l,t[x].r=r;
    if(l==r){
        t[x].sum=t[x].lnum=t[x].rnum=t[x].num=a[l];
        return ;
    }ll mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);
}
void update(ll x,ll l,ll r,ll pos,ll v){
    if(t[x].l==t[x].r){
        t[x].sum=t[x].lnum=t[x].rnum=t[x].num=v;
        return ;
    }ll mid=(l+r)/2;
    if(pos<=mid) update(x*2,l,mid,pos,v);
    else update(2*x+1,mid+1,r,pos,v);
    pushup(x);
}
node problem(ll x,ll l,ll r,ll L,ll R){
    if(L<=l&&r<=R) return t[x];
    ll mid=(l+r)/2;
    if(R<=mid) return problem(x*2,l,mid,L,R);
    if(L>mid) return problem(x*2+1,mid+1,r,L,R);
    node res,fl=problem(x*2,l,mid,L,R),fr=problem(x*2+1,mid+1,r,L,R);
    res.sum=fl.sum+fr.sum;
    res.lnum=max(fl.lnum,fl.sum+fr.lnum);
    res.rnum=max(fr.rnum,fr.sum+fl.rnum);
    res.num=max({res.lnum,res.rnum,fl.rnum+fr.lnum});
    return res;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        ll opt,x,y;
        cin>>opt>>x>>y;
        if(opt==2) update(1,1,n,x,y);
        else cout<<problem(1,1,n,x,y).num<<endl;
    }
}

by Lawrence003 @ 2024-05-24 17:03:49

主要问题有四处：

1. 你没有判x>y，这会导致无限递归，会造成RE/TLE，但这次就是表现为TLE。
2. pushup函数里的t[x].sum=t[x].sum+t[x].sum，应该是t[x].sum=t[l].sum+t[r].sum。
3. pushup函数里的t[x].num=max({t[x].lnum,t[x].rnum,t[x2].rnum+t[x2+1].lnum})，应该是t[x].num=max({t[x2].num,t[x2+1].num,t[x2].rnum+t[x2+1].lnum})。
4. problem函数里的res.num=max({res.lnum,res.rnum,fl.rnum+fr.lnum})，应该是res.num=max({fl.num,fr.num,fl.rnum+fr.lnum})。

by lutaoquan2012 @ 2024-05-24 17:07:08

@Lawrence001 不明白第三点呀

by lpx2024 @ 2024-06-07 21:33:02

@lutaoquan2012 就是说当前节点最大值应该是左子节点最大值，右子节点最大值和中间拼起来的去一个最大的，你写成了当前节点靠左边的最大值和靠右边的最大值

by Pink_Cut_Tree @ 2024-07-15 09:34:50

@Lawrence001 求调本题 9 分

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define ll long long
#define ls(u) u<<1
#define rs(u) u<<1|1
int n,m;
int a[N],siz[4*N];
ll w[4*N],maxx[4*N],lftmax[4*N],rgtmax[4*N];
int p,s,k;
void pushup(int u){
    w[u]=w[ls(u)]+w[rs(u)];
    maxx[u]=max({maxx[ls(u)],maxx[rs(u)],lftmax[rs(u)]+rgtmax[ls(u)]});
    lftmax[u]=max(lftmax[ls(u)],lftmax[rs(u)]+w[ls(u)]);
    rgtmax[u]=max(rgtmax[rs(u)],rgtmax[ls(u)]+w[rs(u)]);
}
void build(int u,int l,int r){
    siz[u]=r-l+1;
    if(l==r){
        w[u]=maxx[u]=lftmax[u]=rgtmax[u]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(ls(u),l,mid);
    build(rs(u),mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,int pos,int p){
    if(l==r&&r==pos){
        w[u]=maxx[u]=lftmax[u]=rgtmax[u]=p; 
    }
    else if(!(l>pos||r<pos)){
        int mid=l+r>>1;
        modify(ls(u),l,mid,pos,p);
        modify(rs(u),mid+1,r,pos,p);
        pushup(u);
    }
}
ll qry(int u,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return w[u];
    }
    ll ans=0ll;
    int mid=l+r>>1;
    if(L>mid){
        return qry(rs(u),mid+1,r,L,R);
    }
    if(R<=mid){
        return qry(ls(u),l,mid,L,R);
    }
    else{
        pushup(u);
        return max(qry(rs(u),mid+1,r,L,R),qry(ls(u),l,mid,L,R));
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        cin>>k;
        if(k==1){
            cin>>p>>s;
            if(p>s){
                swap(p,s);
            }
            cout<<qry(1,1,n,p,s)<<"\n";
        }
        else{
            cin>>p>>s;
            modify(1,1,n,p,s);
        }
    }
return 0;
}