BZOJ [2212/3702] [[Poi2011]Tree Rotations]/[二叉树]

发布于 2017-07-04  117 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2212

                 http://www.lydsy.com/JudgeOnline/problem.php?id=3702

题意:有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值。可以任意交换每个非叶子节点的左右孩子。使得最终所有叶子节点的权值按照中序遍历写出来,逆序对个数最少。


考虑到对于交换只在同一个父亲下的左右儿子发生,子树内都是互相独立的。

即交换只能改变两个子树间的逆序对数,所以可以自底向上的一个个去考虑。针对每个叶子开一个权值线段树,向上考虑的过程就是线段树合并的过程。

合并的过程可以顺便选择要不要换,统计答案即可

 


一个非常弱的准退役OIER