我可能学了假的 FHQ Treap

想必大佬的 merge 函数都是这么写的吧：

CPP

int merge(int x,int y)
{
	if(!x||!y)return x+y;
	if(pri[x]<pri[y]){rc[x]=merge(rc[x],y);maintain(x);return x;}
	else{lc[y]=merge(x,lc[y]);maintain(y);return y;}
}

本人对 FHQ Treap 的理解：随机优先级的存在只是为了 让合并更加随机 。

所以本人的 merge 函数一般是这么写的：

CPP

int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(rand()&1){rc[x]=merge(rc[x],y);maintain(x);return x;}
    else{lc[y]=merge(x,lc[y]);maintain(y);return y;}
}

这种写法让我飞到了 P3987 我永远喜欢珂朵莉~ 最优解的第二页。而据我所知，用时比我更短的评测记录大多都比我少测了几个 hack 数据。

但是，今天我做 P3960 列队时，这种写法使我 T 成了 65 分。下载数据后本地运行，用（递归的总次数）/（调用 merge 和 split 函数的总次数），得出了平衡树的平均树高约为

250

，当我改为第一种写法时，算出的平均树高只有

32

，并通过了此题。

所以，请问各位大佬，我的写法有问题吗？

我可能学了假的 FHQ Treap

讨论操作

回复

相关推荐

我可能学了假的 FHQ Treap