在我的线段树合并的代码中我写出了如下的代码:
inline int merge(int x,int y,int l,int r){
if (!x || !y) return x + y;
if (!ls(x) && !rs(x)){
tr[x].sum += tr[y].sum;
delnode(y);
return x;
}
int mid = l + r >> 1;
ls(x) = merge(ls(x),ls(y),l,mid),rs(x) = merge(rs(x),rs(y),mid + 1,r);
delnode(y);
pushup(x);
return x;
}
然而它 WA 了,于是学习 OI-wiki 的写法,写出了如下的代码:
inline int merge(int x,int y,int l,int r){
if (!x || !y) return x + y;
if (l == r){
tr[x].sum += tr[y].sum;
delnode(y);
return x;
}
int mid = l + r >> 1;
ls(x) = merge(ls(x),ls(y),l,mid),rs(x) = merge(rs(x),rs(y),mid + 1,r);
delnode(y);
pushup(x);
return x;
}
然而,它们之间的区别就在于 (!ls(x) && !rs(x)) -> (l == r),我认为这是没有区别的 。于是对它们 assert 了一下发现:
如果满足 !ls(x) && !rs(x),但 l 不一定与 r 相等。
如果满足 l=r,一定满足 (!ls(x) && !rs(x))。
为什么/ll