线段树求调 有考虑交换 but 9pts AC #1

LeNotFound @ 2022-12-02 10:35:44

by LeNotFound @ 2022-12-02 10:35:52

#include<bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

inline long long read()
{
    long long x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll maxn=5e5+10;

ll a[maxn];

ll w[maxn*4];   // 区间和

ll val[maxn*4]; // 最大子段和

ll lsum[maxn*4];    // 左起最大子段和

ll rsum[maxn*4];    // 右起最大子段和

void pushup(ll u)
{
    w[u]=w[u*2]+w[u*2+1];
    val[u]=max({val[u*2],val[u*2+1],rsum[u*2]+lsum[u*2+1]});
    lsum[u]=max(lsum[u*2],val[u*2]+lsum[u*2+1]);
    rsum[u]=max(rsum[u*2+1],rsum[u*2]+val[u*2+1]);
}

void build(ll u,ll L,ll R)
{
    if(L==R)
    {
        w[u]=val[u]=lsum[u]=rsum[u]=a[L];
        return ;
    }
    ll M=(L+R)>>1;
    build(u*2,L,M);
    build(u*2+1,M+1,R);
    pushup(u);
}

bool inrange(ll L,ll R,ll l,ll r)
{
    return L>=l && R<=r;
}

ll query(ll u,ll L,ll R,ll l,ll r)
{
    ll M=(L+R)>>1;
    if(inrange(L,R,l,r))
    {
        return val[u];
    }
    else if(r<=M)
    {
        return query(u*2,L,M,l,r);
    }
    else if(l>M)
    {
        return query(u*2+1,M+1,R,l,r);
    }
    else if(l<=M && r>M)
    {
        ll la=query(u*2,L,M,l,r);
        ll lb=query(u*2+1,M+1,R,l,r);
        w[u]=w[u*2]+w[u*2+1];
        lsum[u]=max(lsum[u*2],val[u*2]+lsum[u*2+1]);
        rsum[u]=max(rsum[u*2+1],rsum[u*2]+val[u*2+1]);
        val[u]=max({la,lb,rsum[u*2]+lsum[u*2+1]});
        return val[u];
    }
    else 
    {
        return LONG_LONG_MIN;
    }
}

void update(ll u,ll L,ll R,ll p,ll x)
{
    if(L==R)
    {
        w[u]=lsum[u]=rsum[u]=val[u]=x;
        return ;
    }
    else 
    {
        ll M=(L+R)>>1;

        if(p<=M)
        {
            update(u*2,L,M,p,x);
        }
        else 
        {
            update(u*2+1,M+1,R,p,x);
        }

        pushup(u);
    }
}

ll n,m;

int main()
{
    n=read();
    m=read();

    for(ll i=1;i<=n;i++)
    {
        a[i]=read();
    }

    build(1,1,n);

    for(ll i=1;i<=m;i++)
    {
        ll k=read();

        if(k==1)
        {
            ll x=read();
            ll y=read();

            if(x>y)
            {
                swap(x,y);
            }

            cout<<query(1,1,n,x,y)<<endl;
        }
        else if(k==2)
        {
            ll x=read();
            ll y=read();

            update(1,1,n,x,y);
        }
    }

    return 0;
}

by As_Snow @ 2022-12-02 11:17:48

@UperFicial 它维护了最大字段和w。

by UperFicial @ 2022-12-02 11:18:00

@LeNotFound 注意看你的 push_up 中 lsum 和 rsum 的转移，一半边是通过 val 转移的，但是 val 是最大子段和啊，不一定连续，应当用区间和 w 来转移。

by UperFicial @ 2022-12-02 11:18:30

@yangzhengqi 它维护的区间和 w 好像并没有用到。

by As_Snow @ 2022-12-02 11:22:52

@LeNotFound 你为什么要在每次查询时修改 val ，查询到的 la lb 不一定是它维护的区间最大值

by As_Snow @ 2022-12-02 11:23:40

@UperFicial 显然

by As_Snow @ 2022-12-02 11:26:52

边查询边修改就离谱

by LeNotFound @ 2022-12-02 11:38:04

改成w了，确实应该是用区间和求出来

void pushup(ll u)
{
    w[u]=w[u*2]+w[u*2+1];
    val[u]=max({val[u*2],val[u*2+1],rsum[u*2]+lsum[u*2+1]});
    lsum[u]=max(lsum[u*2],w[u*2]+lsum[u*2+1]);
    rsum[u]=max(rsum[u*2+1],rsum[u*2]+w[u*2+1]);
}

by LeNotFound @ 2022-12-02 11:48:23

目前改动的有pushup函数 ↑

还有这个查询的区间包含左右子树的 if 分支

    else if(l<=M && r>M)
    {
        ll la=query(u*2,L,M,l,r);
        ll lb=query(u*2+1,M+1,R,l,r);
        w[u]=w[u*2]+w[u*2+1];
        val[u]=max({la,lb,rsum[u*2]+lsum[u*2+1]});
        lsum[u]=max(lsum[u*2],w[u*2]+lsum[u*2+1]);
        rsum[u]=max(rsum[u*2+1],rsum[u*2]+w[u*2+1]);
        return max({la,lb,rsum[u*2]+lsum[u*2+1]});
    }

by LeNotFound @ 2022-12-02 11:56:10

@yangzhengqi 查询的时候遇到区间覆盖左右两个子树的情况要进行和 pushup 相同的操作吧

不边查询边修改样例都过不去

查询到的 la lb 不一定是它维护的区间最大值

那这种情况应该怎么处理 求教