非旋treap哪里来的maintain呀qaq
by yurzhang @ 2019-07-14 12:09:20
%老船长
by sleepyNick @ 2019-07-14 12:17:11
@[yurzhang](/space/show?uid=126486) fhq Treap也有Maintain的吧
by Thomasguo666 @ 2019-07-14 12:22:13
@[CaptainSlow](/space/show?uid=28022)
我有一种不用笛卡尔树 $O(n)$ 建树的方法。
随机优先级的存在只是为了 **让合并更加随机** 。
所以我们可以不设置随机优先级，令 $y$ 合并到 $x$ 的右儿子的概率为 $\frac {siz[x]} {siz[x]+siz[y]}$ ，然后和线段树类似的建树。
by hsfzLZH1 @ 2019-07-14 12:22:38
@[Thomasguo666](/space/show?uid=107935) 替罪羊什么的都有吧
by Thomasguo666 @ 2019-07-14 12:22:41
@[hsfzLZH1](/space/show?uid=43486) orz
by Thomasguo666 @ 2019-07-14 12:22:58
@[hsfzLZH1](/space/show?uid=43486) 这是不是去年集训队论文里那个
by yurzhang @ 2019-07-14 12:47:43
@[hsfzLZH1](/space/show?uid=43486) 当时好像是说fhq可持久化复杂度会假，用这个trick就没问题（虽然我没用这个也过了
by yurzhang @ 2019-07-14 12:48:24
@[Thomasguo666](/space/show?uid=107935) 你fhq的maintain用来做什么呢= =
by yurzhang @ 2019-07-14 12:51:32
@[yurzhang](/space/show?uid=126486) 具体到这一题，维护子树结点个数，权值和，以及求最大子段和需要维护的一些东西。
by hsfzLZH1 @ 2019-07-14 13:07:08