关于 FHQ-Treap
  • 板块学术版
  • 楼主liurz
  • 当前回复3
  • 已保存回复5
  • 发布时间2023/12/29 14:51
  • 上次更新2023/12/29 19:05:17
查看原帖
关于 FHQ-Treap
171636
liurz楼主2023/12/29 14:51

萌新求问,这是什么复杂度的?QAQ

if(rd[x]<rd[y]) 能起到类似启发式合并的效果吗?

int merge(int x,int y){
	if(!x||!y) return x|y;
	if(rd[x]<rd[y]) swap(x,y);
	int u,v;
	pushdown(x),split(y,u,v,val[x]);
	return lc[x]=merge(lc[x],u),rc[x]=merge(rc[x],v),pushup(x),x;
}

(val 满足 BST 性质,随机权 rd 满足堆性质)

2023/12/29 14:51
加载中...