在query函数中输出空格+过程值后最终输出正确,注释掉后输出错误
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
#define int long long
#define rt 1,1,n
#define mid ((l+r)>>1)
#define L x<<1
#define R x<<1|1
#define Lroot x<<1,l,mid
#define Rroot x<<1|1,mid+1,r
#define WA r<l||r<fl||l>fr
#define AC l>=fl&&r<=fr
int n,m,op,x,y;
int a[N];
struct tree{int ml,mr,ans,sum;}t[N];
void pu(tree &res,const tree &tl,const tree &tr){
if(tl.mr<0&&tr.ml<0)res.ans=max(tl.mr,tr.ml);
else res.ans+=max((int)0,tl.mr),res.ans+=max((int)0,tr.ml);
res.ml=max(tl.ml,tl.sum+tr.ml);
res.mr=max(tr.mr,tr.sum+tl.mr);
res.sum=tl.sum+tr.sum;
res.ans=max(max(tl.ans,tr.ans),res.ans);
}
void build(int x,int l,int r){
if(l==r){
cin>>t[x].ans;
t[x].ml=t[x].mr=t[x].sum=t[x].ans;
return;
}
build(Lroot);
build(Rroot);
pu(t[x],t[L],t[R]);
}
tree query(int x,int l,int r,int fl,int fr){
if(AC)return t[x];
if(fr<=mid)return query(Lroot,fl,fr);
if(fl>mid)return query(Rroot,fl,fr);
tree res;
pu(res,query(Lroot,fl,fr),query(Rroot,fl,fr));
// cout<<" "<<res.ans<<'\n';---correct
// cout<<res.ans<<'\n'; -----wrong
// cout<<""<<res.ans; ----wrong but diff from 1
return res;
}
void update(int x,int l,int r,int fx,int y){
if(l==r){
t[x].ml=t[x].mr=t[x].sum=t[x].ans=y;
return;
}
if(fx<=mid)update(Lroot,x,y);
else update(Rroot,x,y);
pu(t[x],t[L],t[R]);
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
cin>>n>>m;
build(rt);
while(m--){
cin>>op>>x>>y;
if(op==1){
if(y<x)swap(x,y);
tree ans=query(rt,x,y);
cout<<ans.ans<<"\n";
}
if(op==2)update(rt,x,y);
}
return 0;
}
/*
input
5 3
1
2
-3
4
5
1 2 3
2 2 -1
1 2 3
output
20882866
-1
*/