在确定暴力插入的节点是那些时,考虑到每次暴力插入需要进行一次 Split 和两次 Merge 操作,所以为了减小常数,没有使用 Split(tree2,object[i].c*2-1,tree2,tree3)
而是使用 Split(tree2,Max(tree1)+object[i].c,tree2,tree3)
其中 Max 函数的实现如下:
int Max(int u){
Pushdown(u);
if(RS(u))
return Max(RS(u));
return Money(u);
}
按照 FHQ_Treap 的性质,树高大概率是 log(n) 级别的,而 Pushdown 的时间也是常数级别,也就是说这一次 Max 的调用只会增加一点微不足道的常数。
但在实际测试中,第二种做法在 #58 每进行一个操作平均约 0.1s,而第一种做法通过整个测试点只需不到 0.5s。
求助各位大佬,为什么会出现这种情况呢?