Description
You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations: modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
Input
The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
Output
For each query, print an integer as the problem required.
Solution
如果没有修改操作，咋办办呢？我也不知道啊。其实有没有修改都是一个样的呢！
考虑询问，发现对于一段询问的区间l,r，我们如果把它分成两段([l,mid])和((mid,r])。
很容易发现所谓的区间最大连续子段和要么就是在([l,mid])中，要么就是在((mid,r])中，要么就是横跨mid,对于前两种情况，可以分治下去解决。
对于第三种情况，你发现最终答案只会是形如(sum_{i=L}^R a_i (L<=mid<R) Rightarrow sum_{i=L}^{mid} a_i + sum_{i=mid+1}^R a_i)
那么如何对区间进行拆分呢？对于区间问题，我们可以YY线段树，让线段树的每个节点记录该节点代表区间的最大子段和，从左端点开始的最大子段和，到右端点结束的最大子段和。
那么询问，我们可以通过合并([l,r])所包含的区间来得到最终答案（具体过程详见up函数）
其实单点修改很好写，这里也不多做解释，直接上代码
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
int mx,sum,lmx,rmx;
}tre[200000];
int n,a[50010],Q;
void up(node &a,node b,node c)
{
a.sum=b.sum+c.sum;
a.mx=max(b.mx,c.mx);
a.mx=max(a.mx,b.rmx+c.lmx);
a.lmx=max(b.lmx,b.sum+max(c.lmx,0));
a.rmx=max(c.rmx,c.sum+max(b.rmx,0));
}
void build(int p,int l,int r)
{
if (l==r)
{
tre[p].sum=tre[p].mx=tre[p].lmx=tre[p].rmx=a[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(tre[p],tre[p<<1],tre[p<<1|1]);
}
void modify(int p,int l,int r,int pos,int key)
{
if (l==r)
{
tre[p].sum=tre[p].lmx=tre[p].rmx=tre[p].mx=key;
return;
}
int mid=(l+r)>>1;
if (pos<=mid) modify(p<<1,l,mid,pos,key);
else modify(p<<1|1,mid+1,r,pos,key);
up(tre[p],tre[p<<1],tre[p<<1|1]);
}
node query(int p,int l,int r,int i,int j)
{
if (l==i && r==j) return tre[p];
int mid=(l+r)>>1;
if (j<=mid) return query(p<<1,l,mid,i,j);
else if (i>mid) return query(p<<1|1,mid+1,r,i,j);
else
{
node ans;
up(ans,query(p<<1,l,mid,i,mid),query(p<<1|1,mid+1,r,mid+1,j));
return ans;
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&Q);
while (Q--)
{
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if (opt)
{
node ans=query(1,1,n,x,y);
printf("%d
",ans.mx);
}
else modify(1,1,n,x,y);
}
return 0;
}