Tony Zhao

题目大意

给你一个序列，要求支持两种操作：

修改一个值。
查询序号为[l,r]的数中最大的连续子段和。

线段树经典题= =

我们维护以下几个值：包括左端点的最大和，包括右端点的最大和，总和，不限制的最大和。

之后我们单点修改，区间查询，看起来比较恶心但是也不难QwQ

这题最难的地方是query函数里面如果需要查询横跨mid的情况下的最大值查询解决方案。

我们设立2个函数ql(),qr()表示查询包括左端点的最大值和包含右端点的最大值。

之后我们就需要进行特判，然后就可以了。

注意ql(),qr()中的左端点（右端点）（就是保证选择的那个）一定是函数传进去的x(y)也就是说这两个端点一定重合，代码中有冗余见谅。

#include <bits/stdc++.h>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
const int maxN=500010;
int s[maxN<<2],sl[maxN<<2],sr[maxN<<2],sum[maxN<<2],a[maxN],n,m,op,inx,iny;
void pushup(int pos)
{
    sum[pos]=sum[lson]+sum[rson];
    s[pos]=max(max(s[lson],s[rson]),sr[lson]+sl[rson]);
    sl[pos]=max(sl[lson],sum[lson]+sl[rson]);
    sr[pos]=max(sr[rson],sum[rson]+sr[lson]);
    return;
}
void build(int pos,int l,int r)
{
    if(l==r)
    {
        s[pos]=sum[pos]=sl[pos]=sr[pos]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(pos);
    return;
}
void update(int pos,int l,int r,int x,int y)
{
    if(l==r)
    {   
        s[pos]=sum[pos]=sl[pos]=sr[pos]=y;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(lson,l,mid,x,y);
    if(x>mid) update(rson,mid+1,r,x,y);
    pushup(pos);
    return;
}
int ql(int pos,int l,int r,int x,int y)
{
    //printf("ql:%d %d %d %d %d\n",pos,l,r,x,y);
    if(x<=l&&r<=y) return sl[pos];
    int mid=(l+r)>>1;
    if(x>mid) return ql(rson,mid+1,r,x,y);
    if(y<=mid) return ql(lson,l,mid,x,y);
    return max(ql(lson,l,mid,x,y),sum[lson]+ql(rson,mid+1,r,x,y));
}
int qr(int pos,int l,int r,int x,int y)
{
    //printf("qr:%d %d %d %d %d\n",pos,l,r,x,y);
    if(x<=l&&r<=y) return sr[pos];
    int mid=(l+r)>>1;
    if(x>mid) return qr(rson,mid+1,r,x,y);
    if(y<=mid) return qr(lson,l,mid,x,y);
    return max(qr(rson,mid+1,r,x,y),sum[rson]+qr(lson,l,mid,x,y));
}
int query(int pos,int l,int r,int x,int y)
{
    int mid=(l+r)>>1;
    if(x<=l&&r<=y) return s[pos];
    if(x>mid) return query(rson,mid+1,r,x,y);
    if(y<=mid) return query(lson,l,mid,x,y);
    int res=-0x3fffff;
    res=max(res,query(lson,l,mid,x,y));
    res=max(res,query(rson,mid+1,r,x,y));
    res=max(res,qr(lson,l,mid,x,y)+ql(rson,mid+1,r,x,y));
    return res;
    //printf("q:%d %d %d %d %d %d %d %d\n",pos,l,r,x,y,query(lson,l,mid,x,y),query(rson,mid+1,r,x,y)),qr(lson,l,mid,x,y)+ql(rson,mid+1,r,x,y);
    //printf("---%d\n",max(max(query(lson,l,mid,x,y),query(rson,mid+1,r,x,y)),qr(lson,l,mid,x,y)+ql(rson,mid+1,r,x,y)));
    //return max( max ( query(lson,l,mid,x,y) , query (rson,mid+1,r,x,y) ), qr(lson,l,mid,x,y)+ql(rson,mid+1,r,x,y) );
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",a+i);
    build(1,1,n);
    while(m--)
    {
        scanf("%d%d%d",&op,&inx,&iny);
        if(op==1)
        {
            if(inx>iny) swap(inx,iny);
            printf("%d\n",query(1,1,n,inx,iny));
        }
        if(op==2)    update(1,1,n,inx,iny);
    }
    return 0;
}

BZOJ 1756 小白逛公园

题目大意