博客内食用更佳
这道题的 \(k\le 10\) 其实没什么用,代码区别仅在于手写平衡树和使用内置容器。
这道题让查询与一个节点相连的所有点的信息,所以不难想到并查集。
又因为让查询第 \(k\) 大,所以不难想到平衡树和线段树启发式合并。
至此思路明显。我们对并查集中的每个节点开一个平衡树,每次合并两个点的时候,比较祖先节点的节点个数并进行启发式合并。查询的时候如果不是手写平衡树就遍历容器,然后遍历到第 \(k\) 个的时候就输出即可。
复杂度均摊 \(\mathcal{O}(n\log n)\)。
提交记录
没有回复内容