9pts求助

能过样例。

线段树求带修的区间最大子段和。

9pts 求助。

#include<bits/stdc++.h>
#define Mm int mid=(l+r)>>1
#define lc(x) (x<<1)
#define rc(x) ((x<<1)|1)
using namespace std;
struct node{
    int lsum,rsum,sum,maxn;
    node () {}
    node (int a,int b,int c,int d){lsum=a,rsum=b,sum=c,maxn=d;}
};
int sum[2000005],lsum[2000005],rsum[2000005],maxn[2000005],a[500005],n,m;
void build(int l,int r,int now)
{
    if(l==r)
    {
        sum[now]=lsum[now]=rsum[now]=maxn[now]=a[l];
        return ;
    }
    Mm;
    build(l,mid,lc(now));
    build(mid+1,r,rc(now));
    sum[now]=sum[lc(now)]+sum[rc(now)];
    lsum[now]=max(lsum[lc(now)],sum[lc(now)]+lsum[rc(now)]);
    rsum[now]=max(rsum[rc(now)],rsum[lc(now)]+sum[rc(now)]);
    maxn[now]=max(max(maxn[lc(now)],maxn[rc(now)]),rsum[lc(now)]+lsum[rc(now)]);
}
void modify(int l,int r,int now,int situ,int val)
{
    if(l==r && l==situ)
    {
        sum[now]=lsum[now]=rsum[now]=maxn[now]=val;
        return ;
    }
    Mm;
    if(mid>=situ)   modify(l,mid,lc(now),situ,val);
    else    modify(mid+1,r,rc(now),situ,val);
    sum[now]=sum[lc(now)]+sum[rc(now)];
    lsum[now]=max(lsum[lc(now)],sum[lc(now)]+lsum[rc(now)]);
    rsum[now]=max(rsum[rc(now)],rsum[lc(now)]+sum[rc(now)]);
    maxn[now]=max(max(maxn[lc(now)],maxn[rc(now)]),rsum[lc(now)]+lsum[rc(now)]);
}
node query(int l,int r,int x,int y,int now)
{
    if(x<=l && r<=y)    return node(lsum[now],rsum[now],sum[now],maxn[now]);
    Mm;
    if(y<=mid)  return query(l,mid,x,y,lc(now));
    if(mid+1<=x)    return query(mid+1,r,x,y,rc(now));
    node quest1=query(l,mid,x,y,lc(now)),quest2=query(mid+1,r,x,y,rc(now)),ans=node();
    ans.sum=quest1.sum+quest2.sum;
    ans.lsum=max(quest1.lsum,quest1.sum+quest2.lsum);
    ans.rsum=max(quest2.rsum,quest2.sum+quest1.rsum);
    ans.maxn=max(max(quest1.maxn,quest2.maxn),quest1.rsum+quest2.sum);
    return ans;
}
int main(){
//  freopen("P4513_2.in","r",stdin);
//  freopen("T.txt","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)   scanf("%d",&a[i]);
    build(1,n,1);
    while(m-->0)
    {
        int k,A,b;
        scanf("%d %d %d",&k,&A,&b);
        if(k==1)
        {
            if(A>b) swap(A,b);
            printf("%d\n",query(1,n,A,b,1).maxn);
        }
        else    modify(1,n,1,A,b);
    }
    return 0;
}