关于 FHQ _Treap 运行时间的疑惑

CF702F T-Shirts

Diwanul @ 2022-01-07 09:02:06

在确定暴力插入的节点是那些时，考虑到每次暴力插入需要进行一次 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。

求助各位大佬，为什么会出现这种情况呢？

by Tom俩 @ 2022-01-07 10:05:07

@Diwanul 有没有这样一种可能：#58就只有5个操作

by Diwanul @ 2022-01-07 10:15:37

@Tom俩 不是。CF只给出数据前一小部分，我是观察数据的前一小部分的规律来自己造了同类型的数据范围开满的hack数据来测试的。

by Diwanul @ 2022-01-07 10:17:27

另： #58 的构造方式是

每个 c 为 1 或 300000000，其他数据全部随机。

by IwannaAKIOI @ 2023-01-15 17:35:45

看一看您的pushdown有没有避免把信息下传到0号结点

如果下传了，会发现0号结点的Money值是不正确的，这个时候如果您Max函数的初始的u是0，那么就会返回Money(0)显然也是不正确的值

要改的话，可以加一个特判：

Split(tree2,tree1?Max(tree1)+object[i].c:0,tree2,tree3)
|