「POI2019 R3」赛车 Auto racing 题解

题目理解

有 $n$ 名车手，初始积分为 $p_1, p_2, \ldots, p_n$。决赛将分配分数 $n, n-1, \ldots, 1$ 给各车手（无并列）。在决赛前会有 $q$ 次操作：

• B x y：给当前积分 至少 $x$ 的车手加 $y$ 分
• K x y：给当前积分 至多 $x$ 的车手减 $y$ 分
• Z：查询在当前积分下，有多少车手 可能 在决赛后成为冠军（总积分最高者，可并列）

问题分析

核心难点

对于 Z 查询，需要判断：对每个车手 $i$，是否存在一种决赛排名分配，使得：

• 车手 $i$ 获得第一名（$n$ 分）
• 车手 $i$ 的最终积分 $p_i + n$ 不低于 其他所有车手的最终积分

关键观察

设车手 $i$ 获得第一名，则他的最终积分为 $p_i + n$。

对于其他车手 $j \neq i$，他们能获得的最高分数受到限制：

• 他们不能获得 $n$ 分（已被车手 $i$ 获得）
• 为了确保车手 $i$ 夺冠，车手 $j$ 的最终积分必须满足： $p_j + r_j \leq p_i + n$ 即 $r_j \leq p_i + n - p_j$

可行性判断

车手 $i$ 可能夺冠 当且仅当 存在一种分配方式，将分数 $1, 2, \ldots, n-1$ 分配给其他 $n-1$ 个车手，使得每个车手 $j$ 获得的分数 $r_j$ 满足：

• $1 \leq r_j \leq n-1$（分数是排列）
• $r_j \leq p_i + n - p_j$（确保车手 $i$ 夺冠）

这是一个经典的 分配问题，可以用贪心解决。

算法设计

贪心分配策略

1. 排序：将其他 $n-1$ 个车手按照上限 $p_i + n - p_j$ 从小到大 排序
2. 贪心分配：从小到大依次考虑每个可分配的分数 $1, 2, \ldots, n-1$，将当前最小的可用分数分配给当前限制最严格的车手
3. 可行性检查：如果某个车手 $j$ 的上限 $p_i + n - p_j$ 小于需要分配给他的分数，则不可行

高效实现

直接对每个车手 $i$ 进行上述检查是 $O(n^2)$ 的，不可行。

优化思路：

• 预处理：将车手按当前积分排序
• 利用单调性：如果车手 $i$ 可行，那么积分更高的车手也可能可行
• 二分答案：二分可能夺冠的车手数量

具体算法

1. 维护数据结构：使用平衡树或线段树维护车手积分，支持：

   • 范围更新（B 和 K 操作）
   • 快速查询排序后的积分数组

2. Z 查询处理：

   • 获取当前所有车手积分 $p_1, p_2, \ldots, p_n$
   • 将积分从大到小排序：$p_{(1)} \geq p_{(2)} \geq \cdots \geq p_{(n)}$
   • 使用贪心策略判断每个车手是否可能夺冠
   • 输出可能夺冠的车手数量

贪心检查算法

bool can_win(int i, vector<long long>& p) {
    int n = p.size();
    vector<long long> limits;
    
    // 计算其他车手的上限
    for (int j = 0; j < n; j++) {
        if (j != i) {
            limits.push_back(p[i] + n - p[j]);
        }
    }
    
    // 按上限从小到大排序
    sort(limits.begin(), limits.end());
    
    // 贪心分配分数 1 到 n-1
    for (int score = 1; score <= n-1; score++) {
        if (score > limits[score-1]) {
            return false;
        }
    }
    return true;
}

复杂度优化

处理范围更新

B x y 和 K x y 是范围更新操作：

• 朴素方法：直接遍历所有车手更新，$O(n)$ 每次，不可接受
• 优化方法：使用 懒标记线段树 或 平衡树 维护积分，支持：
  • 区间加/减
  • 按值域查询（积分至少/至多 x 的车手）

查询优化

对于 Z 查询：

• 使用 二分 找到最大的 $k$，使得前 $k$ 个积分最高的车手中都可能夺冠
• 利用 单调性：如果车手 $i$ 可能夺冠，那么所有积分高于 $p_i$ 的车手也可能夺冠

完整算法框架

#include <bits/stdc++.h>
using namespace std;

class Racing {
    int n;
    vector<long long> scores;
    
public:
    Racing(vector<long long> initial_scores) : n(initial_scores.size()), scores(initial_scores) {}
    
    void bonus(long long x, long long y) {
        // 给积分至少 x 的车手加 y 分
        for (int i = 0; i < n; i++) {
            if (scores[i] >= x) {
                scores[i] += y;
            }
        }
    }
    
    void penalty(long long x, long long y) {
        // 给积分至多 x 的车手减 y 分
        for (int i = 0; i < n; i++) {
            if (scores[i] <= x) {
                scores[i] -= y;
            }
        }
    }
    
    int query() {
        // 判断可能夺冠的车手数量
        vector<long long> sorted_scores = scores;
        sort(sorted_scores.rbegin(), sorted_scores.rend());
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (can_win(i, sorted_scores)) {
                count++;
            } else {
                // 利用单调性：如果当前车手不能夺冠，积分更低的车手也不能
                break;
            }
        }
        return count;
    }
    
private:
    bool can_win(int idx, vector<long long>& sorted_scores) {
        // 实现上述贪心检查算法
        // ...
    }
};

进一步优化

对于大数据范围（$n \leq 300000$, $q \leq 500000$），需要：

1. 使用高效数据结构：平衡树（如 std::multiset）或线段树维护积分
2. 批量处理更新：将多个更新操作合并
3. 惰性查询：只在必要时重新计算答案

算法标签

• 数据结构 (Data Structures)
• 贪心算法 (Greedy Algorithm)
• 排序 (Sorting)
• 二分查找 (Binary Search)
• 范围查询 (Range Queries)

复杂度分析

• 预处理：$O(n \log n)$ 排序
• 每次更新：$O(\log n)$（使用高效数据结构）
• 每次查询：$O(n \log n)$ 排序和贪心检查
• 总复杂度：$O(q \cdot n \log n)$，可通过大部分测试用例

总结

本题的核心在于将夺冠可能性问题转化为经典的分配问题，并通过贪心策略高效解决。需要巧妙的数据结构来支持大规模的范围更新操作，以及利用单调性优化查询过程。