为啥操作 1 之后会把没涉及到的部分清零呢 | 线段树求调

LeNotFound @ 2022-11-23 02:23:58

by LeNotFound @ 2022-11-23 02:24:29

代码包括调试语句

#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=1e6+10;

const ll inf=LONG_LONG_MAX;

ll a[maxn];
ll w[maxn*4];

ll lzx[maxn*4];
ll lzy[maxn*4];

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

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

void makemtag(ll u,ll x)
{
    w[u]=x;
    lzx[u]=x;
    lzy[u]=0;
}

void makeptag(ll u,ll x)
{
    w[u]+=x;
    if(lzx[u]!=inf)
    {
        lzx[u]+=x;
    }
    else 
    {
        lzy[u]+=x;
    }
}

void pushdown(ll u)
{
    if(lzx[u]!=inf)
    {
        makemtag(u*2,lzx[u]);
        makemtag(u*2+1,lzx[u]);
        lzx[u]=inf;
    }
    else if(lzy[u])
    {
        makeptag(u*2,lzy[u]);
        makeptag(u*2+1,lzy[u]);
        lzy[u]=0;
    }
}

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

bool outofrange(ll L,ll R,ll l,ll r)
{
    return L>r || R<l;
}

void modify(ll u,ll L,ll R,ll l,ll r,ll x)
{
    if(inrange(L,R,l,r))
    {
        makemtag(u,x);
    }
    else if(!outofrange(L,R,l,r))
    {
        pushdown(u);
        ll M=(L+R)>>1;
        modify(u*2,L,M,l,r,x);
        modify(u*2+1,M+1,R,l,r,x);
        pushup(u);
    }
}

void add(ll u,ll L,ll R,ll l,ll r,ll x)
{
    if(inrange(L,R,l,r))
    {
        makeptag(u,x);
    }
    else if(!outofrange(L,R,l,r))
    {
        pushdown(u);
        ll M=(L+R)>>1;
        add(u*2,L,M,l,r,x);
        add(u*2+1,M+1,R,l,r,x);
        pushup(u);
    }
}

ll query(ll u,ll L,ll R,ll l,ll r)
{
    if(inrange(L,R,l,r))
    {
        return w[u];
    }
    else if(!outofrange(L,R,l,r))
    {
        pushdown(u);
        ll M=(L+R)>>1;
        return max(query(u*2,L,M,l,r),query(u*2+1,M+1,R,l,r));
    }
    else 
    {
        return LONG_LONG_MIN;
    }
}

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 op=read();

        if(op==1)
        {
            ll l=read();
            ll r=read();
            ll x=read();

            modify(1,1,n,l,r,x);
            // Debug 输出当前序列状态
            for(ll j=1;j<=n;j++)
            {
                cout<<query(1,1,n,j,j)<<" ";
            }
            cout<<endl;
        }
        else if(op==2)
        {
            ll l=read();
            ll r=read();
            ll x=read();

            add(1,1,n,l,r,x);
            // Debug 输出当前序列状态
            for(ll j=1;j<=n;j++)
            {
                cout<<query(1,1,n,j,j)<<" ";
            }
            cout<<endl;
        }
        else if(op==3)
        {
            ll l=read();
            ll r=read();

            cout<<query(1,1,n,l,r)<<endl;
        }
    }

    return 0;
}

by LeNotFound @ 2022-12-08 17:56:40

在 ChatGPT 的帮助下，我 AC 了这道题

by LeNotFound @ 2022-12-08 17:58:10

当我把代码喂给 ChatGPT 之后……

首先，您在线段树中定义了两个变量lzx和lzy，用来存储区间修改操作的标记。lzx存储区间修改为特定值的操作，lzy存储区间加上特定值的操作。当您需要对一个区间执行修改操作时，您会先判断该区间是否已经被完全修改过，如果已经被完全修改过，那么您直接更新节点中的区间信息即可。如果该区间没有被完全修改过，那么您会递归地修改子区间，并在修改完成后更新节点中的区间信息。

但是，您在更新节点信息时，只是更新了区间修改为特定值的操作，没有考虑区间加上特定值的操作。这就导致了在执行完区间修改操作之后，区间外的值被清空为0的问题。为了解决这个问题，您可以在更新节点信息时，同时更新区间修改为特定值的操作和区间加上特定值的操作。例如，在更新节点信息时，您可以这样写：

w[u]=max(w[u*2],w[u*2+1]);
lzx[u]=inf;
lzy[u]=0;

区间修改操作之后，您的线段树会正确地更新区间信息，并且不会清空区间外的值。

当然，您还需要注意其他可能导致问题的地方。例如，在查询区间信息时，您需要先下传标记，以便获得正确的结果。还有，在对一个节点执行修改操作时，您需要注意清空该节点的修改标记。

如果您还有疑问，可以在下一条消息中给出您的代码，我会继续为您提供帮助。

在调用maketag函数之后，您需要更新线段树节点u所表示的区间信息。例如，如果您使用了上面我提供的代码，您可以这样写：

void pushup(ll u)
{
    w[u]=max(w[u*2],w[u*2+1]);
    lzx[u]=inf;
    lzy[u]=0;
}

这样，您的线段树节点会正确地更新区间信息，并且不会清空区间外的值。

如果您还有疑问，可以在下一条消息中给出您的代码，我会继续为您提供帮助。

by LeNotFound @ 2022-12-08 18:01:29

此贴完结

by Spasmodic @ 2022-12-08 18:41:02

？？？？？？？？？？？？？？？？？