7.1 lxl DS Day1 题解

7.1 lxl DS Day1 题解

P7124 [Ynoi2008] stcm

性质1： 考虑轻儿子的子树和为 \(O(nlogn)\)。

证明： 考虑每个结点会对多少个轻祖先做贡献， 也就是重链个数， 考虑每个节点到根节点重链条数为 \(O(nlogn)\) ， 所以子树和为 \(O(nlogn)\)。

所以对于一条重链， 如果我们已经插入了链头的补集， 那么我们就可以直接暴力插入和删除求出这条重链上所有点的答案， 然后对于重链上轻儿子的答案， 我们可以如果可以得到轻儿子的补集， 就可以递归下去了。

考虑对于重链上所有轻儿子怎么搞， 可以对于所有轻儿子建出霍夫曼树， 然后遍历每个叶子节点， 可以证明轻儿子子树和为 \(O(n)\) 的话， 这一步操作时间复杂度为所有节点带权子树和， 为 \(O(nlogn)\)。

证明： 考虑每个叶子节点对祖先的贡献， 考虑这是一课霍夫曼树， 每往上走一层子树大小至少翻倍， 所以树高\(logn\)， 子树和就是 \(O(nlogn)\)。

P2325 [SCOI2005] 王室联邦

考虑这是树分块的板子题，构造过程：

1. 从节点 \(u\) dfs搜索下去， 考虑 \(u\) 为省会， 所以遍历了超过 \(B\) 节点就直接分为一块， 直到剩下一小坨的节点数小于 \(B\)， 把 \(u\) 也带上， 分给 \(u\) 的 \(father\)。
2. 对于 \(father\)， 也是递归上述过程。

P8204 [Ynoi2005] tdnmo

考虑树上邻域查询不删除莫队， 考虑树分块， 类似王室联邦的构造， 但是为了保证簇只有两个界点， 所以考虑多加一个限制就是， 如果最后剩下的儿子大于等于2个， 所以直接令 \(u\) 为界点， 虽然这样多了一些 \(siz\) 小于 \(B\)， 但是考虑可以证明不影响复杂度， 所以树分块直接就成功了， 这是最简单的建法了吧。

然后考虑回滚莫队， 所以考虑 \(x\) 不在簇路径上的点，直接从空集到询问， 反正不会超过 \(O(\sqrt n)\)。

考虑在簇路径上的点， 直接回滚到下界点， 跑回滚莫队就行了。

P4475 巧克力王国

半平面数点， 可以用kdt， 但是数据不随机会被卡掉， 并且数据随机时， 可以有这个做法：

对于平面分块， 分成 \(\sqrt n \times \sqrt n\) 的块， 每个块期望的点数是 \(O(1)\) 的， 所以考虑对于与直线有交的残块， 直接暴力查询 \(O(\sqrt n)\) ， 对于整块， 做一下前缀和即可。

P9996 [Ynoi2000] hpi

同样可以半平面数点， 对于右上/左下的半平面， 统计每个右上/左下的点数。对于右下/左上的半平面， 容斥一下即可。