这是 100opt 的写法,可持久化fhq中在 split 函数中 pushdown 在 copy 前面:
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);
}
}
这是 4opt 的写法,在 split 函数中 copy 在 pushdown 前面:评测记录
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);
}
}
完整的 100opt 代码:剪贴板。
同学说先 copy 再 pushdown 会导致新版本下放了懒标记但是旧版本还没有下放。但是我觉得这不应该会影响正确性啊,我的代码在 pushdown 时会新建两个子节点,新版本和旧版本的懒标记不会互相影响啊。
我和同学花了近一个小时一边讨论一边画图,觉得先 copy 再 pushdown 感性上是有问题,但是理性画图分析怎么画图怎么对。
请问各位大佬,可持久化fhq中在 split 函数中为什么 pushdown 要在 copy 前面?如果能画图说明就更好了。谢谢!