query合并左右区间
by UYHW @ 2023-11-05 20:07:03
@[UYHW](/user/252567) 是这样吗，还是不行
```cpp
#include <bits/stdc++.h>
#define For(i,s,e) for(int i=s;i<=e;i++)
#define dFor(i,s,e) for(int i=s;i>=e;i--)
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;
struct node{
int l,r,m,s;
};
const int MaxN=1145141;
int n,q,a[MaxN],ans[4][MaxN<<2];
void push_up(int p){//0->l 1->r
ans[2][p]=ans[2][ls]+ans[2][rs];
ans[0][p]=max(ans[0][ls],ans[2][ls]+ans[0][rs]);
ans[1][p]=max(ans[1][rs],ans[2][rs]+ans[1][ls]);
ans[3][p]=max(max(ans[3][ls],ans[3][rs]),ans[1][ls]+ans[0][rs]);
}
void build(int p,int l,int r){
if(l==r){
ans[0][p]=ans[1][p]=ans[2][p]=ans[3][p]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
push_up(p);
}
void update(int n,int p,int k,int l,int r){
if(n==l && n==r){
ans[0][p]=ans[1][p]=ans[2][p]=ans[3][p]=k;
return;
}
int mid=(l+r)>>1;
if(n<=mid)update(n,ls,k,l,mid);
if(n>mid)update(n,rs,k,mid+1,r);
push_up(p);
}
node query(int nl,int nr,int l,int r,int p){
if(nl<=l && r<=nr)
return (node){ans[0][p],ans[1][p],ans[3][p],ans[2][p]};
node res;
int mid=(l+r)>>1;
if(nl<=mid)res=query(nl,nr,l,mid,ls);
else if(nr>mid)res=query(nl,nr,mid+1,r,rs);
else if(nl<=mid && nr>mid){
node x=query(nl,nr,l,mid,ls),y=query(nl,nr,mid+1,r,rs);
res.l=max(x.l,x.s+y.l);
res.r=max(y.r,y.s+x.r);
res.m=max(max(x.m,y.m),x.r+y.l);
res.s=x.s+y.s;
return res;
}
return res;
}
signed main(){
scanf("%lld%lld",&n,&q);
For(i,1,n)scanf("%lld",a+i);
build(1,1,n);
while(q--){
int op,a,b;
scanf("%lld%lld%lld",&op,&a,&b);
if(op==2){
update(a,1,b,1,n);
}else if(op==1){
if(b<a)swap(a,b);
printf("%lld\n",query(a,b,1,n,1).m);
}else{
For(o,0,3){
int i=1,j=1,e=1;
while(1){
if(e>(n<<1))break;
for(j=1;j<=1<<(i-1);j++){cout<<ans[o][e++]<<" ";}
cout<<endl;
i++;
}}
}
}
return 0;
}
/*
5 114
1
2
-3
4
5
*/
```
by Dio_The_World @ 2023-11-05 20:34:43
@[UYHW](/user/252567) 过了过了，谢谢巨佬
by Dio_The_World @ 2023-11-05 20:38:30
@[Dio_The_World](/user/879339) 已经过了，顺序不对，应该先判断nl<=mid && nr>mid再判断后面两个
by Dio_The_World @ 2023-11-05 20:39:36