「PA 2020」Bardzo skomplikowany test 题解

算法思路

本题使用递归分解和贪心策略来解决BST旋转的最小次数问题。核心思想是通过比较两棵BST的结构差异，自顶向下地进行旋转操作，将第一棵树转换为第二棵树。

关键观察

1. BST旋转的性质

• 左旋：当节点 $v$ 的右子树为空时才能进行
• 右旋：当节点 $w$ 的左子树为空时才能进行
• 旋转操作保持BST性质

2. 问题分解策略

从根节点开始，比较两棵树对应节点的位置关系：

• 如果位置相同，直接递归处理子树
• 如果位置不同，通过旋转调整位置

代码解析

数据结构定义

struct Tree {
    int rt, ls[N], rs[N];  // 根节点，左子树，右子树
};
Tree A, B;  // 第一棵树和第二棵树

核心递归函数

inline void work(int pa, int pb, bool flag, bool Ln, bool Rn) {
    // pa: 树A当前节点, pb: 树B当前节点
    // flag: 是否强制旋转, Ln/Rn: 左右子树约束

情况分析

情况1：节点位置相同

if (pa == pb && flag) {
    // 强制旋转情况下，直接递归处理子树
    if (B.ls[pb]) work(pb - 1, B.ls[pb], true, true, true);
    if (B.rs[pb]) work(pb + 1, B.rs[pb], true, true, true);
} else if (pa == pb) {
    // 正常情况，递归处理对应子树
    if (B.ls[pb]) work(A.ls[pa], B.ls[pb], Ln, Ln, Ln);
    if (B.rs[pb]) work(A.rs[pa], B.rs[pb], Rn, Rn, Rn);
}

情况2：pa < pb（需要右旋）

else if (pa < pb && flag) {
    Plus(res, pb - pa);  // 累加旋转次数
    
    // 强制旋转后处理子树
    if (B.ls[pb]) work(pb - 1, B.ls[pb], true, true, true);
    if (B.rs[pb]) work(pb + 1, B.rs[pb], true, true, true);
} else if (pa < pb) {
    // 非强制情况，执行一系列右旋
    int pt = pa;
    do {
        pt = A.rs[pt];  // 沿着右子树找到目标位置
        init(A.ls[pt]);
        res += siz[A.ls[pt]];
        search(A.ls[pt], 0);
    } while (pt < pb);
    
    // 重构树结构
    // ... 旋转操作的具体实现
}

情况3：pb < pa（需要左旋）

与情况2对称，执行左旋操作。

辅助函数

inline void init(int pos) {
    // 计算子树大小
    if (!pos) return;
    siz[pos] = 1;
    init(A.ls[pos]), siz[pos] += siz[A.ls[pos]];
    init(A.rs[pos]), siz[pos] += siz[A.rs[pos]];
}

inline void search(int pos, int type) {
    // 搜索并累加旋转代价
    if (!pos) return;
    if (type == 0) {
        Plus(res, siz[A.rs[pos]]);  // 右子树大小作为代价
        search(A.rs[pos], 1);
        search(A.ls[pos], 0);
    } else {
        Plus(res, siz[A.ls[pos]]);  // 左子树大小作为代价
        search(A.ls[pos], 0);
        search(A.rs[pos], 1);
    }
}

算法正确性

旋转代价计算

• 每次旋转的代价与被旋转子树的大小相关
• 通过 search 函数递归计算所有必要的旋转代价
• 使用模运算防止溢出

递归分解保证

• 从根节点开始，逐层分解问题
• 保证每次旋转都满足BST性质
• 通过约束条件避免无效旋转

复杂度分析

• 时间复杂度：$O(n \log n)$，每个节点被处理常数次
• 空间复杂度：$O(n)$，存储树结构和辅助数组

关键技巧

1. 递归分解：将大问题分解为子树问题
2. 贪心选择：每次选择最少的旋转次数
3. 代价预计算：通过子树大小预计算旋转代价
4. 约束传播：通过参数控制旋转的可行性