之前本猫做 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 做法)