不对发错了。。。
```
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
const int MAXN = 50000 + 10;
const int INF = 1000000000;
struct Tree{
int sum , lmax , rmax , cal;
}x[MAXN << 2];
int N , Q , a[MAXN];
void pushup(int rt){
x[rt] . sum = x[lson] . sum + x[rson] . sum;
x[rt] . lmax = max(x[lson] . lmax , x[rson] . lmax + x[lson] . sum);
x[rt] . rmax = max(x[rson] . rmax , x[lson] . rmax + x[rson] . sum);
x[rt] . cal = max(max(x[lson] . cal , x[rson] . cal) , x[lson] . rmax + x[rson] . lmax);
}
void build(int rt , int l , int r){
if(l == r){
x[rt] . sum = x[rt] . lmax = x[rt] . rmax = x[rt] . cal = a[l];
return;
}
int mid = (l + r) >> 1;
build(lson , l , mid);
build(rson , mid + 1 , r);
pushup(rt);
}
void update(int rt , int p , int l , int r , int c){
if(l == r){
x[rt] . sum = x[rt] . lmax = x[rt] . rmax = x[rt] . cal = c;
return;
}
int mid = (l + r) >> 1;
if(p <= mid) update(lson , p , l , mid , c);
else update(rson , p , mid + 1 , r , c);
pushup(rt);
}
Tree query(int rt , int ql , int qr , int l , int r){
if(ql <= l && r <= qr){
return x[rt];
}
Tree a , b , c;
a . sum = a . lmax = a . rmax = a . cal = -INF;
b . sum = b . lmax = b . rmax = b . cal = -INF;
c . sum = 0;
int mid = (l + r) >> 1;
if(ql <= mid) a = query(lson , ql , qr , l , mid) , c . sum += a . sum;
if(qr > mid) b = query(rson , ql , qr , mid + 1 , r) , c . sum += b . sum;
c . cal = max(max(a . cal , b . cal) , a . rmax + b . lmax);
c . lmax = max(a . lmax , b . rmax + a . sum);
if(ql > mid) c . lmax = max(c . lmax , b . lmax);
c . rmax = max(b . rmax , a . rmax + b . sum);
if(qr <= mid) c . rmax = max(c . rmax , a . rmax);
return c;
}
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 , l , r;
scanf("%d%d%d" , &opt , &l , &r);
if(opt == 0){
update(1 , l , 1 , N , r);
}
else if(opt == 1){
printf("%d\n" , query(1 , l , r , 1 , N) . cal);
}
}
return 0;
}
```
by _LiM @ 2018-07-28 10:17:33
@[LiM_817](/space/show?uid=56724)
这是我刚写的代码，希望对你能有帮助
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
#define mid ((l+r)>>1)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
const int maxn=50000+10;
struct node
{
int sum,l,r,m;
}tree[maxn<<2];
int a[maxn],n,q;
int sum[maxn];
inline void pushup(int rt)
{
tree[rt].sum=tree[ls].sum+tree[rs].sum;
tree[rt].l=max(tree[ls].l,tree[ls].sum+tree[rs].l);
tree[rt].r=max(tree[rs].r,tree[rs].sum+tree[ls].r);
tree[rt].m=max(tree[ls].r+tree[rs].l,max(tree[ls].m,tree[rs].m));
}
void build(int rt,int l,int r)
{
if(l==r)
{
tree[rt].sum=a[l];
tree[rt].l=tree[rt].r=tree[rt].m=a[l];
return;
}
build(lson),build(rson);
pushup(rt);
}
int ql(int rt,int l,int r,int L,int R)
{
if(L>R)return 0;
if(L==l&&r==R)return tree[rt].l;
if(R<=mid)return ql(lson,L,R);
if(L>mid)return ql(rson,L,R);
return max(tree[ls].l,tree[ls].sum+ql(rson,mid+1,R));
}
int qr(int rt,int l,int r,int L,int R)
{
if(L>R)return 0;
if(L==l&&r==R)return tree[rt].r;
if(R<=mid)return qr(lson,L,R);
if(L>mid)return qr(rson,L,R);
return max(tree[rs].r,tree[rs].sum+qr(lson,L,mid));
}
int qm(int rt,int l,int r,int L,int R)
{
if(L>R)return 0;
if(L==l&&r==R)return tree[rt].m;
if(R<=mid)return qm(lson,L,R);
if(L>mid)return qm(rson,L,R);
return max(qr(lson,L,mid)+ql(rson,mid+1,R),max(qm(lson,L,mid),qm(rson,mid+1,R)));
}
void update(int rt,int l,int r,int pos,int k)
{
if(l==pos&&r==pos)
{
tree[rt].sum=k;
tree[rt].l=tree[rt].r=tree[rt].m=k;
return;
}
if(pos<=mid)update(lson,pos,k);
else update(rson,pos,k);
pushup(rt);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&q);
int x,y;
int com;
for(int i=1;i<=q;++i)
{
scanf("%d%d%d",&com,&x,&y);
if(com==1)printf("%d\n",qm(1,1,n,x,y));
else update(1,1,n,x,y);
}
}
```
by x_angelkawaii_x @ 2018-07-28 11:31:21