题意分析

题目背景

• 这是一个单败淘汰赛（Knockout Tournament），共有 (2^n) 名选手。
• 比赛配对规则固定：第一轮 ( (1,2), (3,4), \ldots, (2^n-1,2^n) )，胜者晋级下一轮，直到决出冠军。
• 比赛结果用完全二叉树表示：
  • 叶子节点：初始选手。
  • 内部节点：每一轮的胜者，根节点为冠军。

排名规则

• 传递性：若 A 击败 B，B 击败 C，则 A 也击败 C。
• 对每个选手 ( k_i )，需要确定其最高可能排名和最低可能排名：
  • 最高排名：假设所有未被明确击败的选手都比 ( k_i ) 差。
  • 最低排名：假设所有未被明确击败的选手都比 ( k_i ) 好。

输入输出

• 输入：
  • 多组数据，每组数据包括：
  1. ( n )（选手数为 ( 2^n )）。
  2. 比赛结果列表（按轮次从左到右排列）。
  3. 需要查询的选手编号列表。
• 输出：
  • 对每个查询选手，输出其最高和最低排名。

解题思路

步骤1：构建比赛树

1. 树结构设计：

   • 使用完全二叉树存储比赛结果。
   • 叶子节点为初始选手，内部节点为每一轮的胜者。
   • 例如，输入 1 3 5 8 1 8 1（( n=3 )）对应的树：

          1
        /   \
       1     8
      / \   / \
     1   3 5   8
     
     

2. 建树方法：

   • 初始化所有叶子节点（选手编号）。
   • 按轮次填充内部节点（胜者），自底向上构建树。

步骤2：确定最高排名

• 核心思想：选手的最高排名由其到根节点的路径决定。
  • 路径上的所有节点（胜者）必须排在选手之前。
  • 最高排名 = 路径长度 + 1。
• 例子：
  • 选手 2 的路径：2 → 1 → 1 → 1（长度 3），最高排名 = 4？
    修正：实际应为直接击败它的选手数量 + 1。选手 2 直接输给 1（冠军），最高排名 2。

步骤3：确定最低排名

• 核心思想：选手的最低排名由它直接或间接击败的选手数量决定。
  • 最低排名 = 总选手数 - 击败的选手数。
• 例子：
  • 选手 5 击败了 6，最低排名 = 8 - 1 = 7。

步骤4：处理查询

• 对每个查询选手：
  1. 最高排名：
     • 找到从该选手到根节点的路径，统计必须优于它的选手数量。
  2. 最低排名：
     • 统计该选手在树中击败的所有选手（子树大小）。

优化与边界情况

• 冠军的特殊处理：最高和最低排名均为 1。
• 首轮淘汰选手：
  • 最高排名：击败它的选手的排名 + 1。
  • 最低排名：总选手数（假设其他人都比它强）。