UOJ Logo immortalCO的博客

博客

用无旋转 Treap 来写 LCT

2017-02-17 11:18:51 By immortalCO

之前本猫做 http://uoj.ac/problem/173 的时候,发现如果将 Treap 的 size 记为整棵子树(而非当前层)的大小,复杂度好像是对的。之前过不了好像是建树时的 push_up 次数常数过大,我就把初始化改成先不 push_up,建好之后再 push_up,直接用优化成线性;后面改成每次修改完之后才 push_up 后,操作次数就只剩三百多万了。

然后就想用 Treap 来写 LCT,看一看能不能达到同样是 $O(n\log n)$ 的复杂度。本猫用的是非旋转、无权值的 Treap,利用 splitmerge 来维护序列,在 merge 时以 size 作为概率决定哪一个点在上面。

以下以 http://uoj.ac/problem/3 题为例。

结构体

struct Node
{
    Node *p, *l, *r;    // p:为了方便,记录节点父亲;l、r:左右儿子
    int val, max;    // val:自己的权值;max:当前重链上的最大权值
    uint cnt, sum;    // cnt:这个点的所有轻边的子树大小 + 1;sum:当前子树的 cnt 之和
    bool rev;  // 翻转标记
}

为了保证复杂度,本猫采用了“LCT 维护子树大小”的做法,将 cntsum 维护成子树大小,并据此作为 Treap 的随机种子。

access

这是 LCT 的最基本的操作。伪代码如下:

access(node):
    p = node 所在的重链
    q = 空链
    while p != null:
        # 设 b 为 node 的轻儿子
        将 p 所在的重链从 node 处拆分为 a、b 两段(node 是 a 段的末尾)

        # 维护轻边子树大小之和
        node.cnt += b.sum - q.sum
        更新 p 使得其正确维护信息

        # 设 q 为 node 的重儿子
        p = 连接 a、q 
        更新 p 使得其正确维护信息

        # 下一步循环
        q = p
        node = q 的重链顶端的父亲
        p = node 所在的重链

那么我们就要支持对 Treap 进行从某一个点开始拆分以及合并两个 Treap。显然合并就是 merge 操作。我们只需要实现一个自下而上的 split 操作,循环即可实现。注意这些操作中都要维护好每个节点的父亲。

其他 make_rootlinkcut 操作都能利用上述操作实现(link 只需要设置重链父亲并维护 cntcut 需要一次 split)。

效果

提交为 http://uoj.ac/submission/129275 。感觉上速度挺正常的,不比 Splay 版的慢多少(吐槽:同样的代码连续提交两次使用时间差了 0.7s!)。

为了验证我们维护子树大小确实能欧化复杂度,修改 cnt 的维护方式(修改后为 $O(n\log^2n)$)再次提交为 http://uoj.ac/submission/129302 。慢了一倍以上。

但仍然无法查明其复杂度是否低于 $O(n\log^2n)$。

有啥用

可能可以持久化?(然而还要解决 access 拼接次数是均摊的问题……)

可能可以用其他重量平衡树(如旋转版的 Treap)代替这里的非旋转 Treap,能解决更多 SAM + LCT 的题,或更好的解决 BZOJ 4234,甚至出到子树询问和仙人掌上?(之前有过块链 LCT 做法)

评论

Menci
Excuse Me?
ruanxingzhi
先膜一发
AntiLeaf
咦我听说动态树不是有严格logn的实现么(不关我事啊这是黄志翱说的(逃 ps:咱们的IO不一样,没蛤可比性……
Sengxian
第一次学习无旋 Treap 的时候貌似想到过(WC 2016 李建的课),我还问他能不能用无旋 Treap 写 LCT,他说不知道qwq。
OldDriverTree
反正我试了试用其他重量平衡树写LCT 拖了一个月了还没调出来
dram
猫!
Doggu
先%一发
autoint
没有随机性质怎么保证树高?虽然有正确性,但是时间复杂度没有保证
ggbg
@mike
Love_Ziyou
%

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。