#include<bits/stdc++.h> #define size 500005 using namespace std; int a[size]; struct tree { int l,r; ///l,r左右端点 int data; ///data区间最大子序列和 int lmax; ///lmax区间左端点开头的最大连续子序列和 int rmax; ///rmax区间左端点开头的最大连续子序列和 int sum; ///sum区间和 } t[size*4]; void update(int p,int tl,int tr) { t[p].sum=t[p*2].sum+t[p*2+1].sum; t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax); t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax); t[p].data=max(t[p*2].rmax+t[p*2+1].lmax,max(t[p*2].data,t[p*2+1].data)); } void build(int p, int l, int r) { ///当前的节点，左子节点，右子节点 t[p].l=l; t[p].r=r; if(l==r) ///根节点 { t[p].data=t[p].sum=t[p].lmax=t[p].rmax=a[r]; return ; ///从下往上传数据 } int mid=(l+r)>>1; /// build(p*2,l,mid);///建左子树 build(p*2+1,mid+1,r); ///建右子树 t[p].sum=t[p*2].sum+t[p*2+1].sum; t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax); t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax); t[p].data=max(t[p*2].rmax+t[p*2+1].lmax,max(t[p*2].data,t[p*2+1].data)); } void change(int p,int x,int v)//单点修改 { if(t[p].l==t[p].r) { t[p].data=t[p].sum=t[p].lmax=t[p].rmax=v; return ; } int mid=(t[p].l+t[p].r)>>1; if(x<=mid) change(p*2,x,v); else change(p*2+1,x,v); t[p].sum=t[p*2].sum+t[p*2+1].sum; t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax); t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax); t[p].data=max(t[p*2].rmax+t[p*2+1].lmax,max(t[p*2].data,t[p*2+1].data)); } tree ask(int p,int l,int r) { tree tt,tl,tr; if(t[p].l==l&&t[p].r==r) return t[p]; int mid=(t[p].r+t[p].l)>>1; if(r<=mid) return ask(p*2,l,r);// l r mid 访问左区间 else if(l>mid) return ask(p*2+1,l,r); //mid l r 问右区间 else// l mid r 分开讨论 { tl=ask(p*2,l,mid); tr=ask(p*2+1,mid+1,r); tt.sum=tr.sum+tl.sum; tt.data=max(tl.rmax+tr.lmax,max(tl.data,tr.data)); tt.lmax=max(tl.lmax,tl.sum+tr.lmax); tt.rmax=max(tr.rmax,tr.sum+tl.rmax); tt.sum=tr.sum+tl.sum; return tt; } } int main() { int n,m,k,x,y; cin>>n>>m; for(int i=1; i<=n; i++) cin>>a[i]; build(1,1,n); for(int i=1; i<=m; i++) { cin>>k>>x>>y; if(k==1) { if(x>y) swap(x,y); cout<<ask(1,x,y).data<<endl; } else {change(1,x,y);} } // for(int i=1;i<=2*n-1;i++) // { // printf("%d : %d %d %d %d %d %d \n",i,t[i].l,t[i].r ,t[i].lmax,t[i].rmax,t[i].sum,t[i].data); // } }
