Description
给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“1 x y”，查询区间 [x,y] 中的最大连续子段和。
2、“2 x y”，把 A[x] 改成 y。对于每个查询指令，输出一个整数表示答案。
Input
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改。
数据范围
N ≤ 500000，M ≤ 100000
Output
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
Sample Input
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
Sample Output
2
-1
思路
- 线段树维护：区间紧靠左右两端的最大连续子段和，区间的总和，区间跨左右子树的最大连续子段和
- 当前区间的lmax=左子树lmax和或左子树区间和+右子树lmax（rmax同理）
- 极小值-inf注意不能过小，溢出坑死人
代码
#include <iostream>
#include <cstdio>
#define maxn 500005
#define inf 1005
using namespace std;
int n,m,v[maxn];
struct fdfdfd{int l,r,lmax,rmax,amax,sum;}a[maxn<<2];
void pushup(int x)
{
a[x].sum=a[x<<1].sum+a[x<<1|1].sum;
a[x].lmax=max(a[x<<1].lmax,a[x<<1].sum+a[x<<1|1].lmax);
a[x].rmax=max(a[x<<1|1].rmax,a[x<<1|1].sum+a[x<<1].rmax);
a[x].amax=max(max(a[x<<1].amax,a[x<<1|1].amax),a[x<<1].rmax+a[x<<1|1].lmax);
}
void build(int x,int left,int right)
{
a[x].l=left; a[x].r=right;
if(left==right)
{
a[x].lmax=a[x].rmax=a[x].amax=a[x].sum=v[left];
return;
}
int mid=(left+right)>>1;
build(x<<1,left,mid); build(x<<1|1,mid+1,right);
pushup(x);
}
void modify(int x,int u,int d)
{
if(a[x].r<u||a[x].l>u) return;
if(a[x].l==u&&a[x].r==u)
{
a[x].lmax=a[x].rmax=a[x].amax=a[x].sum=d;
return;
}
modify(x<<1,u,d); modify(x<<1|1,u,d);
pushup(x);
}
fdfdfd query(int x,int left,int right)
{
if(a[x].r<left||a[x].l>right) return (fdfdfd){0,0,-inf,-inf,-inf,-inf};
if(left<=a[x].l&&right>=a[x].r) return a[x];
fdfdfd temp1=query(x<<1,left,right),temp2=query(x<<1|1,left,right),temp;
temp.sum=temp1.sum+temp2.sum;
temp.lmax=max(temp1.lmax,temp1.sum+temp2.lmax);
temp.rmax=max(temp2.rmax,temp2.sum+temp1.rmax);
temp.amax=max(max(temp1.amax,temp2.amax),temp1.rmax+temp2.lmax);
return temp;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&v[i]);
build(1,1,n);
while(m--)
{
int f1,f2,f3; scanf("%d%d%d",&f1,&f2,&f3);
if(f1==1)
{
if(f2>f3) swap(f2,f3);
printf("%d
",query(1,f2,f3).amax);
}
else modify(1,f2,f3);
}
return 0;
}