一直觉得自己写作水平比较烂，而且现在也比较懒，大家凑活着看吧
前置知识：Top Tree相关理论
什么是Weight Balanced Top Tree？
就是满足重量平衡性质的Top Tree。
重量平衡的原始定义是，对于任意节点 $u$，其任意孩子节点 $v$，满足 $v$ 的子树大小 $size(v)$ 与 $u$ 的子树大小 $size(u)$ 的比值在常数范围内。
由于严格的重量平衡性质比较难以满足，这里将条件稍微放宽为，每个Top Tree中的节点向上走 $O(1)$ 后，所在节点的子树大小能翻常数倍。后面在一些问题上可以看到这个性质的用处。
静态树上的做法
可以发现流行的全局平衡二叉树就满足重量平衡的性质。
动态树上的做法：期望复杂度
每个点赋个随机权值，一个点的重儿子是子树max最大的那个儿子。
然后再对重链建treap，轻儿子也要用treap按乱序维护。
实链上的分裂合并就是treap的分裂合并，偏好儿子的切换就按子树max的来维护。
link/cut时需要一些额外讨论。
可以证明每个点期望深度为 $O(\log{n})$。
严格来说treap实现的版本不能算重量平衡树，但是在后续一些场景的分析中，表现跟严格复杂度的版本差不多。
动态树上的做法：严格复杂度
子问题：带权重量平衡树
使用平衡树维护带权序列，支持两种操作：
merge(L,x,R)，x是单点。
split(A,k)，表示将树A从位置k处分开。返回三元组(L,x,R)，x是单点，L,R是相应前后缀组成的平衡树。
希望的复杂度：$O(\log\frac{|L|+w(x)+|R|}{w(x)})$ 复杂度维护平衡树的结构，其中 $w(x)$ 是节点 $x$ 的权重，$|L|,|R|$ 是 $L,R$ 的子树大小
维护不变量：
一个大小k的叶子必须在第i层，满足 $2^i<=k<2^{i+2}$。
任意一个第i层的块都要满足size严格小于 $2^{i+2}$。
第i层维护的块序列中，非叶的部分可以由第 $i-1$ 层中连续几个块（可以是一个）合并得到。第i层维护的块中，相邻两个块不能都小于 $2^i$。
可以验证，全树是重量平衡的（每个点往上走 $O(1)$ 步后size就会翻至少 $O(1)$ 倍），进而有两个推论：1.全树深度为 $O(\log{n})$; 2. x的深度为 $O(\log{\frac{n}{w(x)}})$
记一个块的秩为其所在的层，注意一个块所在的层是一个连续区间（因为允许父节点只有一个孩子，可以压起来），所以其秩也是一个连续区间，实现中可以仅存储其左右端点，而无需对每一层新建一个仅有一个儿子的节点。
shrink
传入参数为两个栈和一个中间元素，$st1,st2,a$
两个栈的栈中元素均满足秩从栈顶往下单调递增，并且 $a$ 的秩不超过两个栈的栈顶元素
可以想象a是秩的最低谷，两个栈是从谷底往两侧延伸的山丘，然后我们要从a开始一点一点把中间的坑填平，将栈中节点与 $a$ 一起合并为一棵合法的树。左右两侧的栈中元素需要满足一定的性质来保证能填平。
首先将 $a$ 的秩区间 $[r1,r2]$ 变成 $[r1,r1]$，避免 $a$ 的秩虚高
每次对于谷底所在的层i，要把连续的若干个秩为i的元素合并成秩为i+1的元素，执行如下贪心策略：
- 如果 $\frac{元素size和}{2^i}<8$，直接合并
- 如果按中位线分开可以分成2半且保证size不超限，按中位线均匀分
- 则先从左到右和从右到左各贪心地切尽量长的一刀，中间剩下的部分再直接贪心切
expand
传入一个栈s，栈中元素均为树中节点。返回另一个栈s'，为将s的栈顶元素u弹掉后再将u的所有儿子按顺序加入栈
merge
将L入栈s。不断对执行 $s \leftarrow expand(s)$，直到s栈顶元素变成叶子或者栈顶元素的秩小于等于 $a$ 的秩。
对R同样操作，然后调用shrink。
split
先将树split成一个单点和两条链。直接将链入栈不可取，需要仿照merge中过程将链中元素给适当展开。
然后将左链和右链的链底的子树截下来，再调用shrink即可。
正确性
shrink过程中唯一可能违反性质的就是，某一轮填平谷底后新元素的size太小，并且此时栈顶元素（也就是未来第i层中的左右邻居）size也太小。
如果此时谷底元素已经有栈中元素参与合成了，由于栈中元素的size原本是满足条件的（是从合法的树中截出来的链），所以此时谷底元素的size一定也合法。
否则如果谷底元素size仍不合法，则在调用shrink前的过程中，栈顶元素一定会被不断expand直到合法。
完整版
用带权重量平衡树作为实链的数据结构，链剖策略使用严格重剖。注意轻子树也使用WCWBT来维护最重的儿子。
access
将一个点到根的链强制变为实链
drop
将实链上的轻边都抖落下去
注意access和drop为都需要注意轻重边切换的顺序，反了的话复杂度是错的；可以使用一个vector存储要切换的边最后再按正确顺序处理。
link/cut时需要一些额外讨论，细节这里略。
最后单次动态树操作的复杂度为严格 $O(\log{n})$，树结构上的静态查询跟普通Top Tree一样做即可。
WBTT能干什么
首先普通Top Tree能干的WBTT基本都能干
其次是一些特殊性质的问题
树分块类的问题
问题形式大概类似于 CTS2022 WBTT
用WBTT维护树结构，对于size小于 $B$ 的子树用 $O(size)$ 的代价维护信息；查询时递归到查询区间中所有size不超过 $B$ 的子树上即可。
重量平衡的性质保证了修改的复杂度，也保证了查询时只会递归到 $O(\frac{n}{B}+\log{n})$ 个子树上，单次复杂度 $O(\sqrt{n})$
以及实际上我们还可以比这题中做得更强，由于Top Tree还给出了块间分治结构，我们在上面跑fractional cascading的话，就可以单次 $O(\sqrt{n})$ 的复杂度解决区间rank上树的问题。
关于treap版本的复杂度分析，
一个引理是，如果树的大小<=B，则从单点 $i$ 往上合并信息的期望代价 $O(B)$。考虑 $j\gt i$ 对 $i$ 的贡献，期望是 $j$ 这个后缀出现的单调栈长度，等于 $H_{n-i+1}-H_{j-i+1}$，其中 $H_i$ 表示调和级数第 $i$项。对求和式稍微放缩一下，可以得到这是 $O(树的大小)$。
完整的分析细节比较冗长，这里略。
小修改动态树上的情形
大概类似于 wcriq 上树的版本，每次修改操作是从树中间裂出一个节点，要求保证单次最坏复杂度并且维护信息。
把wcriq里的做法改改也能上树，细节略。
鄂公网安备 42010202000505 号