，将情况分成两种。
1. 圆环上的数全是正数。所有数字之和减去其中最小的一个数，即为结果。
2. 圆环上的数有负数。此时有两种选取数字的方式：
1. 所选的连续数字包含编号1和n的两个数。此时在线段树内他们并不连续（在1和n之间被断开了）。所有数字之和减去线段树区间内数字最小之和即为结果。
2. 所选的连续数字不包含1和n两个数。用线段树维护出区间内最大连续数字之和即可。
线段树需要维护7个数据：sum, lmax, rmax, tmax, lmin, rmin, tmin。
其中lmax意为从区间左端第一个数开始的最大连续数字之和，rmax意为从区间右端第一个数开始的最大连续数字之和，tmax意为整个区间的最大连续数字之和。 min同理。
至于条件判定，当圆环上全是正数时，对于整个区间有sum=tmax。
***************************************************************************************************************************
1 #include <iostream> 2 #include <string> 3 #include <cstring> 4 #include <cstdio> 5 #include <cmath> 6 #define ls rt<<1 7 #define rs rt<<1|1 8 #define lson l,m,ls 9 #define rson m+1,r,rs 10 #define mid (l+r)>>1 11 #define MAXN 100010 12 using namespace std; 13 int N,M; 14 int a[MAXN]; 15 struct node 16 { 17 int l,r; 18 int lmax,rmax,summax; 19 int lmin,rmin,summin; 20 int sum; 21 }tree[MAXN<<2]; 22 void pushup(int rt) 23 { 24 tree[rt].sum=tree[ls].sum+tree[rs].sum; 25 26 tree[rt].lmax=max(tree[ls].lmax,tree[ls].sum+tree[rs].lmax); 27 tree[rt].rmax=max(tree[rs].rmax,tree[rs].sum+tree[ls].rmax); 28 tree[rt].summax=max(max(tree[ls].summax,tree[rs].summax),tree[ls].rmax+tree[rs].lmax); 29 30 tree[rt].lmin=min(tree[ls].lmin,tree[ls].sum+tree[rs].lmin); 31 tree[rt].rmin=min(tree[rs].rmin,tree[rs].sum+tree[ls].rmin); 32 tree[rt].summin=min(min(tree[ls].summin,tree[rs].summin),tree[ls].rmin+tree[rs].lmin); 33 34 } 35 void build(int l,int r,int rt) 36 { 37 if(l>r)return; 38 tree[rt].l=l; 39 tree[rt].r=r; 40 if(r==l) 41 { 42 tree[rt].sum=a[l]; 43 tree[rt].lmax=tree[rt].lmin=tree[rt].summax=a[l]; 44 tree[rt].rmin=tree[rt].rmax=tree[rt].summin=a[l]; 45 return; 46 } 47 int m=(l+r)>>1; 48 build(lson); 49 build(rson); 50 pushup(rt); 51 } 52 53 void update(int pos,int val,int rt) 54 { 55 if(tree[rt].l==tree[rt].r&&tree[rt].l==pos) 56 { 57 tree[rt].sum=val; 58 tree[rt].lmax=tree[rt].lmin=tree[rt].rmin=tree[rt].rmax=val; 59 tree[rt].summax=tree[rt].summin=val; 60 return; 61 } 62 int m=(tree[rt].l+tree[rt].r)>>1; 63 if(m<pos) 64 update(pos,val,rs); 65 else 66 update(pos,val,ls); 67 pushup(rt); 68 } 69 70 int main() 71 { 72 while(scanf("%d",&N)!=EOF) 73 { 74 for(int i=1;i<=N;i++) 75 scanf("%d",&a[i]); 76 build(1,N,1); 77 78 scanf("%d",&M); 79 int pos,val; 80 81 while(M--) 82 { 83 scanf("%d%d",&pos,&val); 84 update(pos,val,1); 85 86 if(tree[1].sum==tree[1].summax) 87 printf("%d\n",tree[1].sum-tree[1].summin); 88 else 89 printf("%d\n",max(tree[1].summax,tree[1].sum-tree[1].summin)); 90 } 91 } 92 return 0; 93 }
原文：http://www.cnblogs.com/sdau--codeants/p/3528185.html
