【可持久化 fhq_treap】关于代码细节的一个小问题
查看原帖
【可持久化 fhq_treap】关于代码细节的一个小问题
317459
RyexAwl新暗车楼主2022/1/5 22:13

在第一篇题解的 pushdown 代码和 split 代码中:

inline void push_down(int p)
{
	if(!t(p).tag)return;
	if(ls(p))ls(p)=copy_node(ls(p));
	if(rs(p))rs(p)=copy_node(rs(p));
	swap(ls(p),rs(p));
	if(ls(p))tls(p).tag^=1;
	if(rs(p))trs(p).tag^=1;
	tree[p].tag=0;
}
void split(int p,int k,int &x,int &y)
{
	if(!p){x=y=0;return;}
	push_down(p);
	if(tls(p).size<k){x=copy_node(p);split(rs(x),k-tls(p).size-1,rs(x),y);push_up(x);}
	else{y=copy_node(p);split(ls(y),k,x,ls(y));push_up(y);}
}

不难发现是先 pushdown 只会再建的爸爸的新点,而在 pushdown 时只建了儿子的节点。

这种写法是否会影响之前版本信息的正确性?为什么?

2022/1/5 22:13
加载中...