题目大意：
在一个序列上每次改动一个值，然后求出它的最大的子序列和。
思路分析：
首先我们不考虑不成环的问题。那就是直接求每一个区间的最大值就好了。
可是此处成环，那么看一下以下例子。
5
1 -2 -3 4 5
那么你会发现 max = sum - min
也就是和减去最小区间和也能够得到。
所以我们最后要得到的就是两个东西。注意题目中说的不能所有取得。所以还要推断一下max 是不是等于 sum的。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#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;
}