-
831
- 线段树合并
- 把两颗线段树合并为一棵线段树
- 实现操作：若访问到的两个节点中有一个没有元素则返回另一个元素，当访问到叶子节点时合并两个元素即可，通常使用 动态开点线段树来解决
- p4556
- 考虑树上差分，那么对于 \((x, y, z)\) 我们需要将 \(x\) 加上 \((z,1)\) ， \(y\) 加上 \((z, 1)\), \(lca_{x, y}\) 加上 \((z, -1)\), \(fa_{lca_{x, y}}\) 加上 \((z, -1)\) 即可，考虑从根节点开始遍历，儿子节点维护的权值树向当前节点合并，当前节点再加上自己预处理出来的要加的值即可
- 如何证明时空复杂度：可以发现每次合并只会遍历到较小的线段树所以时间和空间复杂度均为 \(O(N log N)\) （因为我们是动态开点的
- P5298
- 考虑对叶子节点的权值进行离散化，之后表示的权值为 \(i\) 即为第 \(i\) 小的权值
- 考虑对每个节点 \(x\) 维护 \(D_x\) 表示 \(x\) 节点权值是 \(i\) 的可能性 \(D_{x,i}\)
- 考虑如何进行维护
- 对于 \(x\) 来说若只有一个儿子或者没有儿子那么直接继承/直接赋值
- 当有两个儿子节点的时候我们记 \(x\) 的左儿子为 \(x_l\) 右儿子为 \(x_r\) \(x\) 取到最大值的概率为 \(p_x\) 最小值的概率为 \(1 - p_x\) 考虑我们的递推式子为 \(D_{x,i} = D_{x_l,i} \cdot p_x \cdot \sum_{j=1}^{i-1} D_{x_r,j} + D_{x_l,i} \cdot (1-p_x) \cdot \sum_{j=x+1}^{n} D_{x_r,j} + D_{x_r,i} \cdot p_x \cdot \sum_{j=1}^{i-1} D_{x_l,j} + D_{x_r,i} \cdot (1-p_x) \cdot \sum_{j=x+1}^{n} D_{x_l,j}\)
- 我们发现如果暴力去进行计算的话那么复杂度是 \(O (N^2)\) 的此时我们考虑进行优化
- 或许一个对于我这种初学者来说比较重要的一点是如何想到线段树合并的
- 结构是从叶子节点向上去合并的符合线段树合并的应用场景
- 可以发现权值使用单点操作无法在有限时间内维护故可以使用线段树的区间操作进行维护
- 更重要的一点是可以发现当一段区间里面只有一个儿子有权值的概率之时，它们的贡献乘上的值都是一样的
- 我们考虑对于每个节点的 \(D\) 数组开一棵权值线段树。
- 当遍历到的区间中左右儿子都有节点那么继续递归
- 考虑只有左/右儿子有节点的情况，设只有左儿子在这个区间中有节点(右儿子同理)，考虑下面这个式子
- \(D_{x,i} = D_{x_l,i} \cdot (p_x \cdot \sum_{j=1}^{i-1} D_{x_r,j} + (1-p_x) \cdot \sum_{j=x+1}^{n} D_{x_r,j})\)
- 我们可以发现关于 \(\sum\) 求和的部分是固定的，那么就变成了一个区间乘的操作可以 \(O(1)\) 解决！
