警示后人(仅 AC #1 #2 #4)
查看原帖
警示后人(仅 AC #1 #2 #4)
595111
In_Memory楼主2024/11/28 22:14

当你 merge 函数是以下写法时:

void merge(int &p1,int p2,int l,int r)
{
    int mid=(l+r)/2;
    if(p1==0)
    {
    	p1=p2;
        return;
    }
    if(p2==0)
        return;
    if(l==r)
    {
        tree[p1].val+=tree[p2].val;
        return;
    }
    merge(tree[p1].lch,tree[p2].lch,l,mid);
    merge(tree[p1].rch,tree[p2].rch,mid+1,r);
    pushup(p1);
}

一定要边 dfs 边处理答案,不能全部合并完后再处理。

原因:当 p1p_1 为空时,会将 p2p_2 的节点直接接到 p1p_1 上。之后合并时若再对 p1p_1 该节点修改,会同步影响 p2p_2 的答案。

不过我觉得这是线段树合并有关两种写法的基础问题,不会有人错吧。

2024/11/28 22:14
加载中...