题目分析

这是一个需要追踪奖牌流转并确定最终归属的问题。关键难点在于：

• 奖牌会随着比赛结果在选手间流转
• 最终奖牌归属由持有时间决定
• 需要高效处理 $M$ 场比赛的连锁反应

算法思路

核心思想

使用逆向处理 + 树形DFS的方法：

1. 逆向建树：从最后一天向前构建比赛关系树
2. DFS统计：在树上DFS统计每个选手持有奖牌的时间
3. 动态维护：维护每个节点的最大持有时间和对应选手

关键观察

• 每场比赛可以看作一个节点，胜者获得败者的所有奖牌
• 比赛过程形成一个树形结构，胜者是父节点，败者是子节点
• 逆向处理可以避免复杂的奖牌流转追踪

代码详解

数据结构定义

const int N = 2e5 + 10;
int n, m;
int s[N];      // s[i]: 第i场比赛的胜者
int in[N];     // in[i]: 选手i最近一次参赛的比赛编号
int ans[N];    // ans[i]: 选手i最终获得的奖牌数
int f[N];      // f[i]: 选手i当前累计持有时间
int vis[N];    // vis[i]: 比赛i是否已访问
int ma[N];     // ma[i]: 节点i的最大持有时间
int id[N];     // id[i]: 节点i对应最大持有时间的选手
vector<int> v[N]; // v[i]: 比赛i的子比赛（败者之前的比赛）

建树过程

cin >> n >> m;
for(int i = 1; i <= m; i++) {
    int &a = s[i], b;
    scanf("%d%d", &a, &b);
    a++, b++;  // 转换为1-indexed
    
    // 构建比赛关系树
    if(in[a]) v[i].push_back(in[a]);  // 胜者之前的比赛作为子节点
    if(in[b]) v[i].push_back(in[b]);  // 败者之前的比赛作为子节点
    
    in[a] = i;  // 更新胜者最近参赛记录
    in[b] = 0;  // 败者失去所有奖牌，清空记录
}

DFS统计过程

void dfs(int x, int y) {
    vis[x] = 1;
    
    // 更新当前胜者的持有时间
    f[s[x]] += y - x;  // 从比赛x到比赛y的持有时间
    
    // 更新最大持有时间和对应选手
    if(f[s[x]] > ma[x]) {
        ma[x] = f[s[x]];
        id[x] = s[x];
    } else if(f[s[x]] == ma[x] && s[x] < id[x]) {
        id[x] = s[x];  // 时间相同时选择编号小的
    }
    
    // 统计奖牌（每场比赛产生一枚奖牌）
    ans[id[x]]++;
    
    // 递归处理子比赛
    for(int i : v[x]) {
        ma[i] = ma[x];    // 继承父节点的最大时间
        id[i] = id[x];    // 继承父节点的最佳选手
        dfs(i, x);        // 递归处理，x作为新的结束时间
    }
    
    // 回溯：减去当前胜者的持有时间
    f[s[x]] -= y - x;
}

主流程

// 从最后一天向前处理
for(int i = m; i >= 1; i--) {
    if(!vis[i]) {
        dfs(i, m + 1);  // 从比赛i处理到比赛结束
    }
}

// 输出结果
for(int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
}

算法原理

逆向建树的意义

• 每个比赛节点代表一枚奖牌的流转路径
• 父节点继承子节点的所有奖牌
• 逆向处理可以自然处理奖牌的累积效应

持有时间计算

• f[player] 记录选手当前累计持有时间
• y - x 表示从比赛 x 到比赛 y 的时间段
• 在DFS过程中动态累加和回溯

奖牌归属决策

• ma[x] 记录节点 x 的最大持有时间
• id[x] 记录对应最佳选手
• 根据题目规则：时间最长 → 编号最小

复杂度分析

时间复杂度

• 建树：$O(M)$
• DFS遍历：$O(M)$
• 总复杂度：$O(M)$

空间复杂度

• $O(N + M)$ 存储各种数组和邻接表

样例分析

样例1执行过程

输入：

3 4
0 1
2 1  
1 0
2 1

建树过程：

• 比赛1：胜者1(0)，败者2(1)
• 比赛2：胜者3(2)，败者2(1)
• 比赛3：胜者2(1)，败者1(0)
• 比赛4：胜者3(2)，败者2(1)

DFS统计后得到正确结果：1 1 2