AGC023 F: 01 on Tree
树上拓扑序最小逆序对;按块中 0/1 数量比贪心,把最优块并入父块,优先队列加并查集维护。来源 AtCoder AGC023 F · 时间 2 s,空间 256 MB · 标签 贪心 / 树 / 并查集 / 优先队列 / 逆序对
题目描述
有一棵以 为根的有根树,第 个点上写着 。把树上的点排成一个序列,要求任意点的所有祖先都排在它的左边。设从左到右读出的 01 序列为 ,求 的最小逆序对数。
。
题解
把当前已经绑定为连续一段的点称为一个块。块 记录其中 的个数 和 的个数 。初始时每个点单独成块。
若两个相邻块 没有祖先关系,比较“ 在 前”和“ 在 前”的代价。二者只差跨块逆序对:
因此 应排在 前,当且仅当
于是采用如下贪心:每次取当前非根块中 最大的块 ,把它并入父块 。若 在 前,跨块产生的逆序对为
合并后块的计数为 、。
正确性来自交换论证。设 是当前比值最大的块, 是它的父块。若 与 之间还有块 ,把 向左跨过 。由于 ,跨块逆序对不增加,因此可以让 紧跟在 后面而不变劣。把 绑定到 是安全的;重复此过程即可。
实现上,用优先队列维护块的比值,用并查集找到当前父块。取出的块若已被合并或就是根块,则跳过。合并时累加 ,更新计数,并把新的父块重新入队。
块的比值为 时排在最后,比值为无穷时排在最前;比较比值要交叉相乘,避免浮点误差。
复杂度
优先队列和并查集均为 ,空间 。答案需要 位整数。
参考
- 题目链接:AtCoder AGC023 F 01 on Tree。
- 思路参考:Sshwy AGC 笔记。