题解：POI 2011 Tree Rotations

问题本质

给一棵二叉树，每个叶子有唯一编号（1~n）。可以交换任意内部节点的左右子树（旋转），目标是让中序遍历叶子序列的逆序对最少。

核心思路

对每个节点，左右子树内部的最优逆序对数可以递归求出。

节点处的选择只影响跨左右子树的逆序对，与左右子树内部顺序无关。

跨子树逆序对数量可以通过合并左右子树的权值线段树时计算得出。

关键结论

设节点 u 的左右子树叶子值集合为 L 和 R，大小分别为 a 和 b：

不旋转时跨子树逆序对 cross = ∑{x∈L} ∑{y∈R} [x > y]

旋转时跨子树逆序对 cross_rev = ∑{x∈L} ∑{y∈R} [x < y]

因为 cross + cross_rev = a*b，所以只需计算其中一个。

算法流程

递归处理：DFS 遍历树的输入格式

线段树合并：每个节点维护其子树叶子值的权值线段树（值域 1~n）

合并时计算：

合并左右子树的线段树时，同时计算 cross

cross = 左子树中大于右子树当前值的元素个数，在合并过程中累加

决策：

节点 u 的逆序对数 = inv_left + inv_right + min(cross, a*b - cross)

选择 cross 或 cross_rev 中较小的作为跨子树逆序对 时间复杂度 线段树合并总复杂度 O(n log n)

空间复杂度 O(n log n)