机器人马拉松（Robomarathon）题解

题目分析

核心问题

给定N名机器人选手在N条分道上的马拉松比赛，每条分道的发令喇叭可开关。信号以每秒1道的速度传递，选手i的起跑时间x_i由其分道是否发炮及信号传递时间决定，冲线时间f_i = a_i + x_i。需根据p值（1=最好名次，2=最差名次）计算每位选手的最优或最差排名（排名规则：冲线时间相同并列，时间越短排名越前）。

关键观察

1. 起跑时间x_i的本质：x_i是选手i到最近发炮分道的距离（绝对值）。因为信号从发炮分道向左右传递，每秒1道，所以x_i = min{|i - k| | k是发炮分道}。

2. 冲线时间f_i的变形：f_i = a_i + min{|i - k|}。根据发炮分道的选择，min{|i - k|}可转化为与i相关的线性表达式，进而推导f_i的关键形式：

   • 最好名次（p=1）：需让f_i尽可能小，此时min{|i - k|}可表示为与左右发炮分道相关的边界值，转化为a_i - i和a_i + i的比较。
   • 最差名次（p=2）：需让f_i尽可能大，此时需考虑发炮分道的最优布置，使得更多选手的f_j ≤ f_i。

3. 离散化处理：由于a_i可能达1e9，直接使用a_i相关值作为下标不现实，需对关键值（a_i - i、a_i、a_i + i）进行离散化，方便后续用树状数组（BIT）高效查询。

解题思路

数据预处理

1. 生成关键值：对每位选手i，计算3类关键值：
   • val[0][i] = a_i - i（对应向左传递的信号边界）
   • val[1][i] = a_i（基准值）
   • val[2][i] = a_i + i（对应向右传递的信号边界）
2. 离散化：对3类关键值分别排序、去重，得到离散化后的下标，用于树状数组的索引。

最好名次（p=1）求解

目标：让选手i的f_i最小，此时最优发炮策略是让i的最近发炮分道尽可能近，使得f_i = min(a_i - i + k, a_i + i - k)（k为发炮分道）。转化为统计两类选手的数量：

• 比i的a_i - i小的选手（对应左侧发炮的最优情况）
• 比i的a_i + i小的选手（对应右侧发炮的最优情况） 使用两个树状数组分别维护这两类值的计数，通过前缀和查询得到比当前值小的元素个数，即为排名的基础（+1得到最终排名）。

最差名次（p=2）求解

目标：让选手i的f_i最大，此时最优发炮策略是让i的最近发炮分道尽可能远，使得f_i = a_i + d（d为最大可能的最近距离）。需考虑三类情况：

1. 仅右侧有发炮分道的情况
2. 仅左侧有发炮分道的情况
3. 左右两侧均有发炮分道的情况（中间区域的最大距离） 通过三个树状数组分别维护不同区域的关键值，结合滑动窗口技巧处理中间区域的最大距离情况，最终取三类情况的最大值作为排名基础（+1得到最终排名）。

数据结构选择

使用树状数组（BIT）高效支持：

• 单点更新（添加/删除某个关键值的计数）
• 前缀和查询（统计小于当前值的元素个数） 时间复杂度为O(N log N)，可满足n=4e5的大数据需求。

完整代码

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

int n;
struct BIT {
    int c[400010], maxn;
    BIT() {
        memset(c, 0, sizeof c);
    }
    void update(int id, int x) {
        for (int i = id; i <= maxn; i += i & (-i))
            c[i] += x;
    }
    int cx(int id, int res = 0) {
        for (int i = id; i >= 1; i -= i & (-i))
            res += c[i];
        return res;
    }
} t[3];

int a[400010], p;
int val[3][400010], x[3][400010], len[3], ans[400010];
int op[3] = {0, -1, 1};  // 对应val[0]=a+i*0=a, val[1]=a+i*(-1)=a-i, val[2]=a+i*1=a+i

// 获取离散化后的下标，d为偏移量（用于最差名次的中间区域计算）
int get_val(int id, int i, int d = 0) {
    int x = a[i] + i * op[id] + d;
    return lower_bound(val[id] + 1, val[id] + len[id] + 1, x) - val[id];
}

// 初始化离散化后的下标数组x
void init() {
    for (int i = 0; i < 3; i++)
        for (int j = 1; j <= n; j++)
            x[i][j] = get_val(i, j);
}

// 求解最好名次（p=1）
void solve1() {
    // 初始化树状数组t[2]（维护a+i的离散化值）
    for (int i = 1; i <= n; i++)
        t[2].update(x[2][i], 1);

    // 遍历每个选手，计算比当前选手优的数量
    for (int i = 1; i <= n; i++) {
        t[2].update(x[2][i], -1);  // 移除当前选手自身
        // 统计a-j < a-i（t[1]）和a+k < a+i（t[2]）的选手数量
        ans[i] = t[1].cx(x[1][i] - 1) + t[2].cx(x[2][i] - 1);
        t[1].update(x[1][i], 1);  // 将当前选手加入t[1]
    }
}

// 求解最差名次（p=2）
void solve2() {
    // 情况1：仅右侧有发炮分道，统计a+k < a+i的数量
    for (int i = 1; i <= n; i++)
        t[2].update(x[2][i], 1);
    for (int i = 1; i <= n; i++)
        ans[i] = t[2].cx(x[2][i] - 1);
    // 清空t[2]，初始化t[1]（维护a-j）
    for (int i = 1; i <= n; i++) {
        t[2].update(x[2][i], -1);
        t[1].update(x[1][i], 1);
    }

    // 情况2：仅左侧有发炮分道，统计a-j < a+i的数量，取最大值
    for (int i = 1; i <= n; i++) {
        ans[i] = max(ans[i], t[1].cx(x[1][i] - 1));
        t[1].update(x[1][i], -1);
    }

    // 情况3：左右两侧均有发炮分道，中间区域的最大距离情况
    // t[0]维护a，t[1]维护a-j，t[2]维护a+k
    for (int i = 2; i <= n; i++)
        t[0].update(x[0][i], 1);
    int P = 0, P1 = 2;  // P：左侧窗口边界，P1：右侧窗口边界

    for (int l, i = 2; i < n; i++) {
        l = min(n - i, i - 1);  // 中间区域的最大可能距离

        // 扩展右侧窗口：将[i, i+l]加入t[1]（a-j）
        while (P1 < i + l) {
            t[0].update(x[0][P1], -1);
            t[1].update(x[1][P1], 1);
            P1++;
        }

        t[1].update(x[1][i], -1);  // 移除当前选手自身
        t[2].update(x[2][i - 1], 1);  // 将左侧分道i-1加入t[2]

        // 收缩左侧窗口：将[P+1, i-l-1]加入t[0]（a）
        while (P < i - l) {
            P++;
            t[2].update(x[2][P], -1);
            t[0].update(x[0][P], 1);
        }

        // 计算三类区域中比当前f_i小的选手数量，更新最大值
        ans[i] = max(ans[i], t[0].cx(get_val(0, i, l) - 1) + t[1].cx(x[1][i] - 1) + t[2].cx(x[2][i] - 1));
    }
}

// 输出结果（排名=比当前选手优的数量+1）
void print() {
    for (int i = 1; i <= n; i++)
        cout << ans[i] + 1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // 生成三类关键值
        for (int j = 0; j < 3; j++)
            val[j][++len[j]] = a[i] + i * op[j];
    }

    // 离散化处理：排序+去重
    for (int i = 0; i < 3; i++) {
        sort(val[i] + 1, val[i] + len[i] + 1);
        len[i] = unique(val[i] + 1, val[i] + len[i] + 1) - val[i] - 1;
        t[i].maxn = len[i];  // 设置树状数组的最大下标
    }

    init();  // 初始化离散化后的下标
    if (p == 1)
        solve1();
    else
        solve2();
    print();

    return 0;
}

代码说明

1. 树状数组（BIT）：实现高效的单点更新和前缀和查询，用于统计特定范围内的元素个数。
2. 离散化：处理大数值范围，将关键值映射到连续的小下标，降低空间复杂度。
3. 分情况求解：
   • 最好名次：通过两个树状数组分别统计左右两侧最优发炮策略下的更优选手数量。
   • 最差名次：考虑三种发炮策略（仅左、仅右、左右均有），通过滑动窗口维护中间区域，取最大值作为更优选手数量。
4. 效率优化：时间复杂度O(N log N)，空间复杂度O(N)，可处理n=4e5的大数据量，满足题目要求。