萌新刚学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-23 16:46:51

用啥cin啊

by lutaoquan2012 @ 2024-05-23 22:46:08

@Lawrence001 因为习惯用cin

by Lawrence003 @ 2024-05-24 16:24:14

第一眼没看到是你啊

by Lawrence003 @ 2024-05-24 16:28:30

奇怪，开了scanf之后还是TLE

by Lawrence003 @ 2024-05-24 16:44:27

调了但是WA了

by Lawrence003 @ 2024-05-24 16:50:30

你没有判x>y

by Lawrence003 @ 2024-05-24 16:52:50

还有你的pushup里的t[x].sum=t[x].sum+t[x].sum;

by Lawrence003 @ 2024-05-24 16:54:47

t[x].num=max({t[x].lnum,t[x].rnum,t[x2].rnum+t[x2+1].lnum});和res.num=max({res.lnum,res.rnum,fl.rnum+fr.lnum});不对

by Lawrence003 @ 2024-05-24 16:56:34

AC了，代码：

//test lutaoquan2012
#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];
inline void pushup(ll x){
    t[x].sum=t[x*2].sum+t[x*2+1].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*2].num,t[x*2+1].num,t[x*2].rnum+t[x*2+1].lnum});
}
inline 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);
}
inline 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);
}
inline 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({fl.num,fr.num,fl.rnum+fr.lnum});
    return res;
}
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        ll opt,x,y;
        scanf("%lld%lld%lld",&opt,&x,&y);
        if(opt==2) update(1,1,n,x,y);
        else
        {
            if(x>y)swap(x,y);
            printf("%lld\n",problem(1,1,n,x,y).num);
        }
    }
}

by Lawrence003 @ 2024-05-24 17:02:12

主要问题有三处： 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})。