开始懵逼找不到解法，看了网上大牛们的题解才发现是区间合并。。。
给你n个数形成一个数列环，然后每次进行一个点的修改，并输出这个数列的最大区间和（注意是环，并且区间最大只有n-1个数）
其实只需要维护：最大区间的值 mmax，最小区间的值 mmin。当然要维护这两个值就需要维护：左端点开始的最大与最小区间的值，右端点开始的最大与最小区间的值。然后是数列的总和，数列的最大值，最小值。然后就是查询时的区间最大值等于整个区间的mmax和区间和sum减去mmin，但是当都是非负数，都是负数时要特判。亏我刷了那么多线段树还是没有看出来，果然还是自己太弱
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const double Pi=acos(-1.0);
const int Max=<<;
struct node
{
int mmax,lmax,rmax,mmin,lmin,rmin;
int sum,manx,minx;
void init(int num)
{
mmax=lmax=rmax=mmin=lmin=rmin=manx=minx=sum=num;
}
} segtr[Max];
int non;//非负数个数
int nmin(int a,int b)
{
return a>b?b:a;
}
int nmax(int a,int b)
{
return a>b?a:b;
}
void Upnow(int now,int next)//关键
{
segtr[now].minx=nmin(segtr[next].minx,segtr[next|].minx);//区间最值需要运用线段树
segtr[now].manx=nmax(segtr[next].manx,segtr[next|].manx);
segtr[now].sum=segtr[next].sum+segtr[next|].sum; segtr[now].lmax=nmax(segtr[next].lmax,segtr[next].sum+segtr[next|].lmax);//左端点开始的区间最大值可能跨左右区间
segtr[now].rmax=nmax(segtr[next|].rmax,segtr[next|].sum+segtr[next].rmax);
segtr[now].mmax=nmax(nmax(segtr[next].mmax,segtr[next|].mmax),segtr[next].rmax+segtr[next|].lmax);//区间最大值也可能是跨左右区间的最大值 segtr[now].lmin=nmin(segtr[next].lmin,segtr[next].sum+segtr[next|].lmin);
segtr[now].rmin=nmin(segtr[next|].rmin,segtr[next|].sum+segtr[next].rmin);
segtr[now].mmin=nmin(nmin(segtr[next].mmin,segtr[next|].mmin),segtr[next].rmin+segtr[next|].lmin);
return;
}
void Create(int sta,int enn,int now)
{
if(sta==enn)
{
scanf("%d",&segtr[now].sum);
if(segtr[now].sum>=)
non++;
segtr[now].init(segtr[now].sum);
return;
}
int mid=dir(sta+enn,);
int next=mul(now,);
Create(sta,mid,next);
Create(mid+,enn,next|);
Upnow(now,next);
return;
}
void Update(int sta,int enn,int now,int x,int y)
{
if(sta==enn&&sta==x)
{
if(segtr[now].sum>=&&y<)
non--;
if(segtr[now].sum<&&y>=)
non++;
segtr[now].init(y);
return;
}
int mid=dir(sta+enn,);
int next=mul(now,);
if(mid>=x)
Update(sta,mid,next,x,y);
else
Update(mid+,enn,next|,x,y);
Upnow(now,next);
return;
}
int main()
{
int n,m;
int pos,val;
while(~scanf("%d",&n))
{
non=;
Create(,n,);
scanf("%d",&m);
for(int i=; i<m; i++)
{
scanf("%d %d",&pos,&val);
Update(,n,,pos,val);
if(non==n)//全为非负数
printf("%d\n",segtr[].sum-segtr[].minx);
else if(non==)
printf("%d\n",segtr[].manx);
else
printf("%d\n",nmax(segtr[].mmax,segtr[].sum-segtr[].mmin));//环的处理可以用和减去区间最小值
}
}
return ;
}