请问split中为啥pushdown要在copy前面?
查看原帖
请问split中为啥pushdown要在copy前面?
557756
Brilliance_Z楼主2023/1/27 21:32

这是 100opt100opt 的写法,可持久化fhq中在 split 函数中 pushdowncopy 前面:

void split(int u,int k,int &a,int &b)
{
    if(!u) {a=b=0; return;}
    pushdown(u);//
    if(tr[tr[u].ls].sz<k)
    {
        a=copy(u);
        // pushdown(a);//
        split(tr[a].rs,k-tr[tr[u].ls].sz-1,tr[a].rs,b);
        pushup(a);
    }
    else{
        b=copy(u);
        // pushdown(b);//
        split(tr[b].ls,k,a,tr[b].ls);
        pushup(b);
    }
}

这是 4opt4opt 的写法,在 split 函数中 copypushdown 前面:评测记录

void split(int u,int k,int &a,int &b)
{
    if(!u) {a=b=0; return;}
    // pushdown(u);//
    if(tr[tr[u].ls].sz<k)
    {
        a=copy(u);
        pushdown(a);
        split(tr[a].rs,k-tr[tr[u].ls].sz-1,tr[a].rs,b);
        pushup(a);//
    }
    else{
        b=copy(u);
        pushdown(b);//
        split(tr[b].ls,k,a,tr[b].ls);
        pushup(b);
    }
}

完整的 100opt100opt 代码:剪贴板

同学说先 copypushdown 会导致新版本下放了懒标记但是旧版本还没有下放。但是我觉得这不应该会影响正确性啊,我的代码在 pushdown 时会新建两个子节点,新版本和旧版本的懒标记不会互相影响啊。

我和同学花了近一个小时一边讨论一边画图,觉得先 copypushdown 感性上是有问题,但是理性画图分析怎么画图怎么对。

请问各位大佬,可持久化fhq中在 split 函数中为什么 pushdown 要在 copy 前面?如果能画图说明就更好了。谢谢!

2023/1/27 21:32
加载中...