关于fhq随机merge的复杂度?

mnzn写平衡树时突发奇想,觉得左偏树既然可以通过随机数来随机合并,是否fhq merge时也可以通过随机数来决定merge顺序

CPP

int merge(int x,int y) {
    if(!x || !y) return x | y;
    down(x); down(y);
    if(rd() & 1) {tr[x].r = merge(tr[x].r,y); up(x); return x;}
    else {tr[y].l = merge(x,tr[y].l); up(y); return y;}
}

然后他就 TLE 了,更改为

CPP

if((tr[x].rk > tr[y].rk))

就不会TLE,考虑过是否是因为取随机数常数太大,因此写过提前生成随机数序列

CPP

if(rd[ctr = (ctr + 1 >= N ? 0 : ctr + 1))

还是会TLE,又尝试了有些直接 0 / 1轮流merge,反而会更快 ?

CPP

if(rdg ^= 1)

输出了一下,发现以上三种方式构造的平衡树都极度不平衡

所以这和提前用 rk 规定好顺序有什么区别 ?

为什么左偏树可以随机合并但平衡树不行 ?

提交记录

关于fhq随机merge的复杂度?

讨论操作

回复

相关推荐

关于fhq随机merge的复杂度?