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 了 谢谢,已关