当你 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 边处理答案,不能全部合并完后再处理。
原因:当 p1 为空时,会将 p2 的节点直接接到 p1 上。之后合并时若再对 p1 该节点修改,会同步影响 p2 的答案。
不过我觉得这是线段树合并有关两种写法的基础问题,不会有人错吧。