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

然后就想用 Treap 来写 LCT，看一看能不能达到同样是 $O(n\log n)$ 的复杂度。本猫用的是非旋转、无权值的 Treap，利用 split 和 merge 来维护序列，在 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 维护子树大小”的做法，将 cnt 和 sum 维护成子树大小，并据此作为 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_root、link、cut 操作都能利用上述操作实现（link 只需要设置重链父亲并维护 cnt，cut 需要一次 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 做法）