juruo999 @ 2021-07-23 15:07:35
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
template <typename T>
void Read(T &x) {
x=0;char c=getchar();
T f=1;
while(c<'0'||c>'9'){ if(c=='-'){f=-1;} c=getchar(); }
x=c-'0';
while((c=getchar())>='0' && c<='9'){ x=x*10+c-'0';}
x*=f;
}
template <typename T, typename... Args>
void Read(T &x, Args &... args) {
Read(x);
Read(args...);
}
const int maxn=500005;
struct node{
int s,l,r,t;
int m;
node(){}
node(int v){
s=v;l=r=t=v;
m=v;
}
};
node v[maxn*4+10],a[maxn];
void pushup(node&x,const node&l,const node&r){
x.s=l.s+r.s;
x.l=max(l.l,l.s+r.l);
x.r=max(r.r,r.s+l.r);
x.t=max(l.t,max(r.t,l.r+r.l));
x.m=max(l.m,r.m);
}
void build(node a[],int l,int r,int id){
if(l==r){
v[id]=a[l];
return;
}
int mid=(l+r)>>1;
build(a,l,mid,id<<1);
build(a,mid+1,r,id<<1|1);
pushup(v[id],v[id<<1],v[id<<1|1]);
}
node query(int x,int y,int id,int l,int r){
if(x<=l && r<=y){
return v[id];
}
int mid=(l+r)>>1;
node res(-0x3f3f3f);
if(x>mid){
res=query(x,y,id<<1|1,mid+1,r);
}else if(y<=mid){
res=query(x,y,id<<1,l,mid);
}else{
pushup(res,query(x,y,id<<1|1,mid+1,r),query(x,y,id<<1,l,mid));
}
return res;
}
void change(int p,node x,int id,int l,int r){
if(l==r){
v[id]=x;
return;
}
int mid=(l+r)>>1;
if(p<=mid){
change(p,x,id<<1,l,mid);
}else{
change(p,x,id<<1|1,mid+1,r);
}
pushup(v[id],v[id<<1],v[id<<1|1]);
}
int main(){
int n,m,k,q,p;
Read(n,m);
for(int i=1;i<=n;i++){
Read(a[i].s);
a[i].l=a[i].r=a[i].t=a[i].s;
a[i].m=a[i].s;
}
build(a,1,n,1);
for(int i=1;i<=m;i++){
Read(k,q,p);
if(k==1){
if(q>p){
swap(q,p);
}
if(query(q,p,1,1,n).m<0){
printf("%d\n",query(q,p,1,1,n).m);
}else{
printf("%d\n",query(q,p,1,1,n).t);
}
}else if(k==2){
change(q,node(p),1,1,n);
}
}
return 0;
}
by Tom俩 @ 2021-07-23 15:12:28
十年OI一场空
by 小杨小小杨 @ 2021-07-23 15:13:33
萌 新 刚 学 线 段 树
我好菜呜呜呜
by juruo999 @ 2021-07-23 15:35:33
A了
by juruo999 @ 2021-08-01 21:48:00
pushup(res,query(x,y,id<<1|1,mid+1,r),query(x,y,id<<1,l,mid));
这句无脑错误……