9pts求助,玄关

P4513 小白逛公园

zk_y @ 2023-11-03 14:00:41

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+1000;
#define ll long long
ll n,m;
ll op,l,r;
struct node{
    ll tot;
    ll max_back;
    ll max_front;
    ll max_tot;
}tree[N<<2];
ll number[N];
void update(ll num){
    tree[num].tot=tree[num<<1].tot+tree[num<<1|1].tot;
    tree[num].max_front=max({tree[num].max_front , tree[num<<1].max_front , tree[num<<1].tot+tree[num<<1|1].max_front});
    tree[num].max_back=max({tree[num].max_back , tree[num<<1|1].max_back , tree[num<<1|1].tot+tree[num<<1].max_back});
    tree[num].max_tot=max({tree[num].max_tot , tree[num<<1].max_back+tree[num<<1|1].max_front , tree[num<<1].max_tot , tree[num<<1|1].max_tot});
    return;
}
void build(ll l,ll r,ll num){
    if(l==r){
        tree[num].tot=number[l];
        tree[num].max_tot=number[l];
        tree[num].max_front=tree[num].max_back=max((ll)0,number[l]);
        return;
    }
    ll mid=(l+r)/2;
    build(l,mid,num<<1);
    build(mid+1,r,num<<1|1);
    update(num);
    return;
}
void change_num(ll pos,ll l,ll r,ll num,ll change_number){
//  cout<<pos<<" "<<change_number<<' '<<l<<' '<<r<<' '<<num<<'\n';
    if(l==r&&l==pos){
        tree[num].tot=change_number;
        tree[num].max_front=tree[num].max_back=max((ll)0,change_number);
        tree[num].max_tot=change_number;
        return;
    }
    if(l>pos||r<pos)return;
    ll mid=(l+r)/2;
    if(mid>=pos)change_num(pos,l,mid,num<<1,change_number);
    else change_num(pos,mid+1,r,num<<1|1,change_number);
    update(num);
    return;
}
ll find_tot(ll want_l,ll want_r,ll l,ll r,ll num){
    if(want_l<=l&&want_r>=r){
//      cout<<want_l<<" "<<want_r<<' '<<l<<' '<<r<<' '<<num<<'\n';
//      cout<<tree[num].max_tot<<'\n';
        return tree[num].max_tot;
    }
    ll ans=-1e9;
    ll mid=(l+r)/2;
    if(want_l<=mid)ans=max(ans,find_tot(want_l,want_r,l,mid,num<<1));
    if(want_r>mid)ans=max(ans,find_tot(want_l,want_r,mid+1,r,num<<1|1));
    update(num);
    return ans;
}
int  main(){
    scanf("%lld %lld",&n,&m);
    for(ll i=1;i<=n;i++)scanf("%lld",&number[i]);
    build(1,n,1);
    for(ll i=1;i<=m;i++){
        scanf("%lld %lld %lld",&op,&l,&r);
        if(op==1){
            if(l>r)swap(l,r);
            printf("%lld\n",find_tot(l,r,1,n,1));
        }
        else{
            change_num(l,1,n,1,r);
        }
    }
    return 0;
}

只对了第一个点。


by Nuclear_Pasta @ 2023-11-03 14:05:43

查询时考虑区间合并


by Wonderful__Answer @ 2023-11-03 15:05:15

显然find_tot写错了 分成3部分,全在左区间,全在右区间,否则合并返回


by zk_y @ 2023-11-04 12:56:06

AC 了 谢谢,已关


|