「BZOJ2212」「POI2011」Tree Rotations-线段树合并

发布于 2018-10-14  82 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「BZOJ2212」「POI2011」Tree Rotations-线段树合并

Description

现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有\(n\)个叶子节点,满足这些权值为\(1..n\)的一个排列)。可以任意交换每个非叶子节点的左右孩子。

要求进行一系列交换,使得最终所有叶子节点的权值按照遍历序写出来,逆序对个数最少。

Solution

考虑交换一个节点的左右儿子对子树外的逆序对没有影响,所以只要考虑子树内的逆序对即可。

那么只需要计算交换前后的逆序对个数然后去\(min\)即可。

所以可以考虑维护左右子树的权值线段树,线段树合并时计算答案即可。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「BZOJ2212」「POI2011」Tree Rotations-线段树合并


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!