AGC023 F: 01 on Tree

树上拓扑序最小逆序对;按块中 0/1 数量比贪心,把最优块并入父块,优先队列加并查集维护。

来源 AtCoder AGC023 F · 时间 2 s,空间 256 MB · 标签 贪心 / 树 / 并查集 / 优先队列 / 逆序对

题目描述

有一棵以 1 为根的有根树,第 𝑖 个点上写着 𝑉𝑖∈{0,1}。把树上的点排成一个序列,要求任意点的所有祖先都排在它的左边。设从左到右读出的 01 序列为 𝑋,求 𝑋 的最小逆序对数。

1≤𝑁≤2×105。

题解

把当前已经绑定为连续一段的点称为一个块。块 𝐵 记录其中 0 的个数 𝐵0 和 1 的个数 𝐵1。初始时每个点单独成块。

若两个相邻块 𝐵,𝐶 没有祖先关系,比较“𝐵 在 𝐶 前”和“𝐶 在 𝐵 前”的代价。二者只差跨块逆序对:

𝐵1𝐶0与𝐶1𝐵0.

因此 𝐵 应排在 𝐶 前,当且仅当

𝐵0𝐵1>𝐶0𝐶1.

于是采用如下贪心:每次取当前非根块中 𝐵0𝐵1 最大的块 𝐵,把它并入父块 𝐴。若 𝐴 在 𝐵 前,跨块产生的逆序对为

𝐴1𝐵0,

合并后块的计数为 𝐴0+𝐵0、𝐴1+𝐵1。

正确性来自交换论证。设 𝐵 是当前比值最大的块,𝐴 是它的父块。若 𝐴 与 𝐵 之间还有块 𝑋,把 𝐵 向左跨过 𝑋。由于 𝐵0𝐵1≥𝑋0𝑋1,跨块逆序对不增加,因此可以让 𝐵 紧跟在 𝐴 后面而不变劣。把 𝐵 绑定到 𝐴 是安全的;重复此过程即可。

实现上,用优先队列维护块的比值,用并查集找到当前父块。取出的块若已被合并或就是根块,则跳过。合并时累加 𝐴1𝐵0,更新计数,并把新的父块重新入队。

块的比值为 0 时排在最后,比值为无穷时排在最前;比较比值要交叉相乘,避免浮点误差。

复杂度

优先队列和并查集均为 𝑂(𝑁log𝑁),空间 𝑂(𝑁)。答案需要 64 位整数。

参考

源码位置