题目：
这个假期，小h在自家院子里种了许多花，它们围成了一个圈，从1..n编号（n<=100000），小h 对每盆花都有一个喜好值xi,（-1000<=xi<=1000）,小h现在觉得这样一成不变很枯燥，于是他做了m(m<=100000)个改动，每次把第ki盘花改成喜好值为di的花，然后小h要你告诉他，在这个花圈中，连续的最大喜好值是多少。
输入：
第一行，n，花盆的数量
第二行，n个数，表示对于每盆花的喜好值。
第三行：m, 改动的次数
以下m行，每行两个数ki 和di 。
输出：
M行，每一行对应一个更改，表示连续的最大喜好值，且不能整圈都选。（注意：是在圈上找）
样例：
5
3 -2 1 2 -5
4
2 -2
5 -5
2 -4
5 -1
4
4
3
5
解法：
线段树（有点复杂）
维护7个值
sum[i]:区间和
smax[i]:最大子段和
smin[i]:最小子段和
lmax[i]:从左端点开始最大的前缀
rmax[i]:从右端点开始最大的前缀
lmin[i]:从左端点开始最小的前缀
rmin[i]:从右端点开始最小的前缀
因为这题不能全部都选，所以如果sum[1]==smax[1]那么就应该输出sum[1]-smin[1]
这七个值的转移可以自己推
#include<cstdio> #include<iostream> using namespace std; int sum[400010],a[100010],sx[400010],sn[400010],rn[400010],ln[400010],rx[400010],lx[400010]; void build(int k,int l,int r) { if (l==r) { sx[k]=sn[k]=sum[k]=rx[k]=lx[k]=rn[k]=ln[k]=a[l]; return; } int mid=l+r>>1; build(k*2,l,mid); build(k*2+1,mid+1,r); sum[k]=sum[k*2]+sum[k*2+1]; sx[k]=max(sx[k*2],max(sx[k*2+1],rx[k*2]+lx[k*2+1])); sn[k]=min(sn[k*2],min(sn[k*2+1],rn[k*2]+ln[k*2+1])); lx[k]=max(lx[k*2],sum[k*2]+lx[k*2+1]); rx[k]=max(rx[k*2+1],sum[k*2+1]+rx[k*2]); ln[k]=min(ln[k*2],sum[k*2]+ln[k*2+1]); rn[k]=min(rn[k*2+1],sum[k*2+1]+rn[k*2]); } void change(int k,int l,int r,int v,int u) { if (l==r&&l==v) { sx[k]=sn[k]=sum[k]=rx[k]=lx[k]=rn[k]=ln[k]=u; return; } int mid=l+r>>1; if (mid>=v) change(k*2,l,mid,v,u); else change(k*2+1,mid+1,r,v,u); sum[k]=sum[k*2]+sum[k*2+1]; sx[k]=max(sx[k*2],max(sx[k*2+1],rx[k*2]+lx[k*2+1])); sn[k]=min(sn[k*2],min(sn[k*2+1],rn[k*2]+ln[k*2+1])); lx[k]=max(lx[k*2],sum[k*2]+lx[k*2+1]); rx[k]=max(rx[k*2+1],sum[k*2+1]+rx[k*2]); ln[k]=min(ln[k*2],sum[k*2]+ln[k*2+1]); rn[k]=min(rn[k*2+1],sum[k*2+1]+rn[k*2]); } int main() { int n,m; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&m); for (register int i=1;i<=m;i++) { int q,p; scanf("%d%d",&q,&p); change(1,1,n,q,p); if (sum[1]==sx[1]) printf("%d ",sum[1]-sn[1]); else printf("%d ",max(sum[1]-sn[1],sx[1])); } }