题意：在一个圈中取若干个相邻的数，求他们的最大序列和。不能够同时取所有的数。
看了一篇解题报告写的很详细。。
1 #include2 #include 3 #include 4 #include 5 const int N=100010; 6 using namespace std; 7 struct node 8 { 9 int l,r,sum,minsum,maxsum;10 int lmax,rmax,lmin,rmin;11 } Tree[4*N];12 int a[N];13 void pushup(int rt)14 {15 int l = 2*rt;16 int r = 2*rt+1;17 Tree[rt].sum=Tree[l].sum+Tree[r].sum;18 Tree[rt].minsum=min(min(Tree[l].minsum,Tree[r].minsum),Tree[l].rmin+Tree[r].lmin);19 Tree[rt].maxsum=max(max(Tree[l].maxsum,Tree[r].maxsum),Tree[l].rmax+Tree[r].lmax);20 Tree[rt].lmax=max(Tree[l].lmax,Tree[l].sum+Tree[r].lmax);21 Tree[rt].rmax=max(Tree[r].rmax,Tree[r].sum+Tree[l].rmax);22 Tree[rt].lmin=min(Tree[l].lmin,Tree[l].sum+Tree[r].lmin);23 Tree[rt].rmin=min(Tree[r].rmin,Tree[r].sum+Tree[l].rmin);24 }25 void build(int l,int r,int rt)26 {27 Tree[rt].l = l;28 Tree[rt].r = r;29 if (l==r)30 {31 Tree[rt].sum=Tree[rt].minsum=Tree[rt].maxsum=a[r];32 Tree[rt].lmax=Tree[rt].rmax=Tree[rt].lmin=Tree[rt].rmin=a[r];33 return ;34 }35 int mid = (l+r)>>1;36 build(l,mid,2*rt);37 build(mid+1,r,2*rt+1);38 pushup(rt);39 }40 void update(int pos,int val,int rt)41 {42 if (Tree[rt].l==Tree[rt].r)43 {44 Tree[rt].sum=Tree[rt].minsum=Tree[rt].maxsum=val;45 Tree[rt].lmax=Tree[rt].rmax=Tree[rt].lmin=Tree[rt].rmin=val;46 return ;47 }48 int mid=(Tree[rt].l+Tree[rt].r)>>1;49 if (pos<=mid)50 update(pos,val,2*rt);51 else52 update(pos,val,2*rt+1);53 pushup(rt);54 }55 int main()56 {57 int n,m,pos,val;58 scanf("%d",&n);59 for (int i = 1; i <=n; i++)60 {61 scanf("%d",&a[i]);62 }63 build(1,n,1);64 scanf("%d",&m);65 while(m--)66 {67 scanf("%d%d",&pos,&val);68 update(pos,val,1);69 if(Tree[1].sum==Tree[1].maxsum)70 {71 printf("%d\n",Tree[1].sum-Tree[1].minsum);72 }73 else74 {75 printf("%d\n",max(Tree[1].maxsum,Tree[1].sum-Tree[1].minsum));76 }77 }78 return 0;79 }