T30720: 败方树的构建与维护

tree, http://cs101.openjudge.cn/practice/30720/

败方树（Loser Tree） 是一种用于多路归并排序的完全二叉树结构。它通过维护每场“比赛”的失败者，使得获取当前所有元素中的最小值以及在修改元素后更新状态的效率达到最优。

构建规则：

叶子结点（外部结点）：数组中的 n 个元素作为败方树的叶子结点。
内部结点：败方树有 n 个内部结点（包含一个位于根部上方的“冠军结点”）。
- 每个内部结点存储该场比赛的败者（数值较大者）。
- 每场比赛的胜者（数值较小者）将继续向上晋级，与父结点中记录的上一轮败者进行比较。
- 根部上方结点：存储最终的全局胜者（冠军）。
树形结构：本题要求构建一棵基于数组位置的完全二叉树。对于 n=8 的情况，第一轮由数组相邻元素 (0,1), (2,3), (4,5), (6,7) 两两对决，胜者进入下一轮，直至选出冠军。

任务： 给定一个长度为 n 的整数数组，构建初始败方树。随后进行 m 次修改操作，每次修改数组中的一个元素，并同步更新败方树。要求输出初始状态及每次修改后，所有内部结点（含冠军结点）代表的数值。

输入

第一行：两个整数 n 和 m。n 代表数组元素个数，m 代表修改次数。第二行：n 个整数，代表数组的初始元素。接下来 m 行：每行包含两个整数 idx 和 val，表示将数组下标为 idx 的元素修改为 val（下标从 0 开始）。

输出

输出共 m+1 行。第一行：初始构建后，败方树内部结点的整数序列。随后 m 行：每次修改后，败方树内部结点的整数序列。注意：输出顺序为内部结点的层次遍历顺序（从上到下，从左到右，第一位是全局冠军）。

样例输入

8 1
10 9 20 6 16 12 90 17
3 15

样例输出

6 12 9 17 10 20 16 90
9 12 15 17 10 20 16 90

#解释第一行输出
第一轮对决 (叶子层)：
10 vs 9 -> 胜者 9, 败者 10；20 vs 6 -> 胜者 6, 败者 20；
16 vs 12 -> 胜者 12, 败者 16；90 vs 17 -> 胜者 17, 败者 90

第二轮对决 (半决赛)：
9 vs 6 -> 胜者 6, 败者 9；12 vs 17 -> 胜者 12, 败者 17

第三轮对决 (决赛)：
6 vs 12 -> 胜者 6, 败者 12

冠军节点： 6

层次遍历内部节点结果： 6 (冠军), 12 (决赛败者), 9 (半决赛败者L), 17 (半决赛败者R), 10, 20, 16, 90 (初始败者)

提示

数据范围：1 <= n <= 10^5，0 <= m <= 10^5，注意：保证 (n+1)×(m+1)≤2×10^6 数组元素为整数。

来源

yan, http://cs101.openjudge.cn/practice/07576/

python

import sys
from collections import deque


class TreeNode:
    # 使用 __slots__ 优化内存
    __slots__ = ['value', 'min_win', 'left', 'right', 'parent']

    # 构造函数支持四个参数及默认值
    def __init__(self, value=0, min_win=0, left=None, right=None):
        self.value = value
        self.min_win = min_win
        self.left = left
        self.right = right
        self.parent = None  # parent 通常在节点关联后设置


def solve():
    # 1. 快速读取
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    it = iter(input_data)
    n = int(next(it))
    m = int(next(it))

    # 2. 构建初始树
    # 初始化叶子：value为0(无意义)，min_win存初始值
    leaves = [TreeNode(0, int(next(it))) for _ in range(n)]
    queue = deque(leaves)

    while len(queue) > 1:
        l = queue.popleft()
        r = queue.popleft()

        # 利用四个参数的构造函数直接创建比赛节点
        # value 存败者(max), min_win 存胜者(min)
        match_node = TreeNode(
            max(l.min_win, r.min_win),
            min(l.min_win, r.min_win),
            l,
            r
        )
        l.parent = r.parent = match_node
        queue.append(match_node)

    # 创建冠军节点 (唯一只有左孩子的内部节点)
    battle_root = queue.popleft()
    root = TreeNode(battle_root.min_win, battle_root.min_win, battle_root)
    battle_root.parent = root

    # 3. 预处理内部节点顺序
    # 核心：必须通过 if node.left 过滤掉可能出现在浅层级的叶子节点
    internal_nodes = []
    bfs_q = deque([root])
    while bfs_q and len(internal_nodes) < n:
        curr = bfs_q.popleft()
        if curr.left:  # 有孩子即为内部节点
            internal_nodes.append(curr)
            bfs_q.append(curr.left)
            if curr.right:  # 只有比赛节点有右孩子，冠军节点没有
                bfs_q.append(curr.right)

    def print_internal_nodes():
        sys.stdout.write(" ".join(str(node.value) for node in internal_nodes) + "\n")

    # 输出初始
    print_internal_nodes()

    # 4. 修改与增量更新 O(log n)
    for _ in range(m):
        try:
            idx = int(next(it))
            new_val = int(next(it))
        except StopIteration:
            break

        curr = leaves[idx]
        curr.min_win = new_val

        p = curr.parent
        while p:
            if p.right:  # 普通比赛节点更新
                p.value = max(p.left.min_win, p.right.min_win)
                p.min_win = min(p.left.min_win, p.right.min_win)
            else:  # 顶层冠军节点更新
                p.value = p.min_win = p.left.min_win
            p = p.parent

        print_internal_nodes()


if __name__ == "__main__":
    solve()

实现败方树（Loser Tree）最稳健、高效的方式是使用数组堆索引映射法。这种方法不仅能完美处理 $n$ 不是 2 的幂次的情况，还能保证其结构始终是一棵完全二叉树，且更新操作的时间复杂度严格控制在 $O (\log n)$ 。

数组实现逻辑

内部结点（tree 数组）：
- tree[0]：存储全局冠军（最小值）。
- tree[1...n-1]：存储每一场比赛的败者（较大值）。
- 数组索引 $0, 1, \dots, n - 1$ 的顺序正好对应完全二叉树的层次遍历顺序。
胜者状态（winners 数组）：
- winners[n...2n-1]：存储 $n$ 个叶子结点。
- winners[1...n-1]：存储每一场比赛产生的胜者，用于向上传递。
完全二叉树性质：
- 对于任何比赛结点 $i$ ，其参与对决的两个子来源索引一定是 $2 i$ 和 $2 i + 1$ 。
- 这保证了即使 $n$ 不是 2 的幂，树也会自动处理“轮空”逻辑。

标准答案代码（Python 实现）

python

import sys

def solve():
    # 使用 sys.stdin.read().split() 解决大规模数据输入速度问题
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        n = int(next(it))
        m = int(next(it))
    except StopIteration:
        return
    
    # winners 数组模拟完全二叉树的所有结点
    # winners[n...2n-1] 是叶子 (外部结点)
    # winners[1...n-1] 是每一层比赛选出的胜者
    winners = [0] * (2 * n)
    for i in range(n):
        winners[n + i] = int(next(it))
        
    # tree 数组存储败方树的内部状态 (按层次遍历顺序)
    # tree[0] 是冠军, tree[1...n-1] 是对应索引比赛的败者
    tree = [0] * n
    
    # 1. 初始构建 (O(n)): 从最后一个比赛结点向上构建
    for i in range(n - 1, 0, -1):
        left_val = winners[2 * i]
        right_val = winners[2 * i + 1]
        
        if left_val <= right_val:
            winners[i] = left_val  # 胜者向上晋级
            tree[i] = right_val    # 败者留在该结点
        else:
            winners[i] = right_val
            tree[i] = left_val
            
    # 全局冠军是根部比赛 (index 1) 的胜者
    if n > 0:
        tree[0] = winners[1]
    
    # 辅助函数：输出 tree 数组的所有内容
    def output_state():
        sys.stdout.write(" ".join(map(str, tree)) + "\n")
        
    # 输出初始构建后的状态
    output_state()
    
    # 2. 增量维护 (O(m log n)): 每次修改只更新受影响的路径
    for _ in range(m):
        try:
            idx = int(next(it))
            val = int(next(it))
        except StopIteration:
            break
            
        # 更新叶子结点
        pos = n + idx
        winners[pos] = val
        
        # 向上追溯更新路径到根比赛结点
        curr = pos // 2
        while curr >= 1:
            l_val = winners[2 * curr]
            r_val = winners[2 * curr + 1]
            
            if l_val <= r_val:
                winners[curr] = l_val
                tree[curr] = r_val
            else:
                winners[curr] = r_val
                tree[curr] = l_val
            curr //= 2
            
        # 更新冠军
        tree[0] = winners[1]
        
        # 输出每次修改后的状态
        output_state()

if __name__ == "__main__":
    solve()

为什么这个方案能 AC？

时间复杂度最优：
- 构建时间： $O (n)$ 。
- 更新时间： $m \times O (\log n)$ 。
- 总时间： $O (n + m \log n)$ 。对于 $2 \times 10^{6}$ 的数据量，在 Python 2 秒的限制内非常充裕。
空间复杂度最优：
- 只使用了两个长度约 $2 n$ 和 $n$ 的数组，没有复杂的对象引用开销。
完全二叉树结构：
- 利用 2i 和 2i+1 的索引规律，自动处理了 $n$ 为任意正整数的情况。
- 层次遍历的输出顺序（冠军 $\to$ 决赛败者 $\to$ 半决赛败者...）正好完全匹配 tree[0...n-1] 的数组存储顺序。
IO 效率：
- 使用了 sys.stdin.read 一次性读取和 sys.stdout.write 批量输出，这是 Python 处理百万级数据的标准做法。

T30720: 败方树的构建与维护 ​

T30720: 败方树的构建与维护