题目大意：

在一个序列上每次修改一个值，然后求出它的最大的子序列和。

思路分析：

首先我们不考虑不成环的问题。那就是直接求每个区间的最大值就好了。

但是此处成环，那么看一下下面样例。

5

1 -2 -3 4 5

那么你会发现 max = sum - min

也就是和减去最小区间和也可以得到。

所以我们最后要得到的就是两个东西。注意题目中说的不能全部取得。所以还要判断一下max 是不是等于 sum的。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define maxn 100005 #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e using namespace std; struct SegTree { int s,e,sum; int lmax,rmax; int lmin,rmin; int mmin,mmax; }ret[maxn<<2]; void pushup(int num){ ret[num].sum=ret[num<<1].sum+ret[num<<1|1].sum; ret[num].lmax=max(ret[num<<1].lmax,ret[num<<1].sum+ret[num<<1|1].lmax); ret[num].lmin=min(ret[num<<1].lmin,ret[num<<1].sum+ret[num<<1|1].lmin); ret[num].rmax=max(ret[num<<1|1].rmax,ret[num<<1|1].sum+ret[num<<1].rmax); ret[num].rmin=min(ret[num<<1|1].rmin,ret[num<<1|1].sum+ret[num<<1].rmin); ret[num].mmax=max(ret[num<<1].rmax+ret[num<<1|1].lmax,max(ret[num<<1].mmin,ret[num<<1|1].mmin)); ret[num].mmin=min(ret[num<<1].rmin+ret[num<<1|1].lmin,min(ret[num<<1].mmin,ret[num<<1|1].mmin)); } void build(int num,int s,int e){ ret[num].s=s,ret[num].e=e; if(s==e){ scanf("%d",&ret[num].lmax); ret[num].sum=ret[num].rmax=ret[num].lmin=ret[num].rmin=ret[num].mmin=ret[num].mmax=ret[num].lmax; return; } int mid=(s+e)>>1; build(lson); build(rson); pushup(num); } void update(int num,int s,int e,int pos,int val){ if(s==e){ ret[num].sum=ret[num].lmax=ret[num].rmax=ret[num].lmin=ret[num].rmin=ret[num].mmin=ret[num].mmax=val; return; } int mid=(s+e)>>1; if(pos<=mid)update(lson,pos,val); else update(rson,pos,val); pushup(num); } int main() { int n; while(scanf("%d",&n)!=EOF){ build(1,1,n); int m; scanf("%d",&m); while(m--){ int pos,v; scanf("%d%d",&pos,&v); update(1,1,n,pos,v); if(ret[1].mmax!=ret[1].sum) printf("%d\n",max(ret[1].mmax,ret[1].sum-ret[1].mmin)); else printf("%d\n",ret[1].sum-ret[1].mmin); } } return 0; }