题意

给出n个数，q次操作，两种操作：把a_x改成y，求[l,r]的最大子段和。

n,m<=50000,-10000<=a_i<=10000

题解

区间问题想到用线段树维护，考虑如何合并区间。

当我们求出两段小区间的最大子段和，那么大区间的最大子段和可能是这两个的其中一个，也可能是中间两个区间拼接的部分，这部分就是左区间右边最大的部分和右区间左边最大的部分组成。

所以我们还需要记录区间紧靠左边和紧靠右边的最大子段和，现在考虑维护左边的最大子段和lmax，在区间合并时，大区间的lmax可能是左区间的lmax，也可能是左边整个区间加上右边区间的lmax。rmax同理。

区间查询的时候传结构体才能合并信息。

 

#include
      
       #include
       
        using namespace std;#define ls rt<<1#define rs rt<<1|1#define ll long longconst int maxn=50005;int n,m;int a[maxn];struct cx{  ll sum,dat,lmax,rmax;// 区间和,区间最大子段和,左端最大子段和,右端最大子段和}t[maxn<<2];ll max(ll x,ll y){
     return x>y ? x : y ;}void get(cx &ret,cx lx,cx ry){  ret.sum=lx.sum+ry.sum;  ret.lmax=max(lx.lmax,lx.sum+ry.lmax);  ret.rmax=max(ry.rmax,ry.sum+lx.rmax);  ret.dat=max(max(lx.dat,ry.dat),lx.rmax+ry.lmax);}void build(int rt,int l,int r){  if(l==r){    t[rt]=(cx){a[l],a[l],a[l],a[l]};    return ;  }  int mid=(l+r)>>1;  build(ls,l,mid);  build(rs,mid+1,r);  get(t[rt],t[ls],t[rs]);}cx query(int rt,int l,int r,int a_l,int a_r){  //printf("%d %d %d %d \n",l,r,a_l,a_r);  if(a_l<=l&&r<=a_r) return t[rt];  int mid=(l+r)>>1;  if(a_r<=mid) return query(ls,l,mid,a_l,a_r);  if(mid
        
         >1;  if(pos<=mid) modify(ls,l,mid,pos,val);  else modify(rs,mid+1,r,pos,val);  get(t[rt],t[ls],t[rs]);}int main(){  scanf("%d",&n);  for(int i=1;i<=n;i++) scanf("%d",&a[i]);  build(1,1,n);  scanf("%d",&m);  for(int i=1;i<=m;i++){    int opt;    scanf("%d",&opt);    if(opt){      int l,r;      scanf("%d%d",&l,&r);      printf("%lld\n",query(1,1,n,l,r).dat);    }    else {      int pos,val;      scanf("%d%d",&pos,&val);      modify(1,1,n,pos,val);    }  }}