CF1790F Timofey and Black-White Tree 题解

World_Creater · 2023-01-31 20:59:18 · 题解

顶级诈骗题。

先放一个重要的结论：在将 x 个点染黑后，答案（即两两黑色点对的最小距离）为 \dfrac{n}{x} 级别（实际上界约为 \dfrac{2n}{x}）。

考虑一个很显然的暴力乱搞，令一个 dis 数组 dis_i 表示离节点 i最近的一个黑色节点。每把一个点染黑，便从这个点开始做一遍搜索更新 dis 数组。若当前节点有更近的黑色节点，或当前节点离新加入的黑色节点的距离大于当前的答案，那么此时继续搜索没有意义，退出。

上述做法正确性显然，同时，这个看上去很假的东西复杂度是对的，为 \mathcal{O}(n\sqrt{n})，同时也是官方题解和 jiangly 的做法。

我们来分析一下复杂度：

首先在经过 \sqrt{n} 次操作后，答案不会超过 \dfrac{n}{\sqrt{n}}=\sqrt{n}，因此所有有意义的 dis_i 的值都不会超过 \sqrt{n}，在我们上述的操作过程中，dis_i 显然是单调不增的，因此在这之后，每个 dis_i 显然也只会被更新 \sqrt{n} 次，因此后面的操作总复杂度是 \mathcal{O}(n\sqrt{n}) 的。而前 \sqrt{n} 操作中，即使每次操作都满打满算单次复杂度 \mathcal{O}(n)，那么 \sqrt{n} 次操作总复杂度也不过是 \mathcal{O}(n\sqrt{n}) 的。

因此该算法的复杂度是 \mathcal{O}(n\sqrt{n}) 的，可以通过本题，如果你超时了请尝试将搜索边界写的紧一点。

以上算法还能继续优化。

每次操作我们都进行一遍搜索的开销太大，我们考虑只进行向上更新，即对于每一个节点，我们一步步跳父亲并更新答案。

这个的正确性看上去不太显然，因为在加入节点时，其子树内的节点是否会被计算到？

答案是会，因为当其子树内部的点存在黑点时，在其向上更新的过程中，也会将这个点计算一遍答案，因此不会出现正确性上的问题。

至于复杂度，由于我们向上跳节点的次数不会超过当前答案（超过了一定不优），因此总复杂度为 \mathcal{O}(\sum_{i=1}^{n}ans_i)，其中 ans_i 为加入第 i 个节点时的答案，初始黑点视为第一个节点。而我们知道 ans_i\leq \dfrac{n}{i}，因此总复杂度为 \mathcal{O}(\sum_{i=1}^{n}\dfrac{n}{i})，这是一个经典的调和级数形式，因此复杂度为 \mathcal{O}(n\log n)，本做法也是 tourist 的做法。

还有很多做法，比如大冤种点分树做法，与 CF342E 类似，不多展开，也是我赛时被诈骗写的做法。

不过个人来看，本题不能完全算与上题重题，因为巧妙利用答案的上界解题思路是这题有而上题没有的。