奇妙节点
查看原帖
奇妙节点
383395
WaterSun楼主2024/1/28 15:01

在我的线段树合并的代码中我写出了如下的代码:

    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 了一下发现:

  1. 如果满足 !ls(x) && !rs(x),但 ll 不一定与 rr 相等。

  2. 如果满足 l=rl = r,一定满足 (!ls(x) && !rs(x))。

为什么/ll

2024/1/28 15:01
加载中...