「ROI 2024 Day2」无人机比赛 题解

题目大意

有 $n$ 架无人机，第 $i$ 架飞行单位距离需要 $t_i$ 秒。
有 $m$ 个门，位置为 $s_1 < s_2 < \dots < s_m$。
比赛规则：无人机从存档点出发，第一个到达某个门的编号最小的无人机存档，其他无人机传送回存档点（算一次传送）。
求对于 $k = 1, 2, \dots, n$，前 $k$ 架无人机参赛时的总传送次数 $c_k$。

思路分析

核心观察

1. 时间计算
   无人机 $i$ 从存档点飞到门 $j$ 所需时间为 $t_i \times (s_j - \text{存档点位置})$。

2. 比赛过程
   每次总是最快到达下一个门的编号最小的无人机获得存档权，其他无人机传送。

3. 问题转化
   可以证明，总传送次数与无人机的相对速度顺序和门间距有关。

算法框架

1. 预处理门间距
   将连续相同间距的门合并为一段，减少计算量。

2. 排序无人机
   按 $t_i \times S_{\max}$ 排序，其中 $S_{\max}$ 是最大门间距，这决定了无人机的相对顺序。

3. 分块数据结构
   使用分块维护两类信息：

   • 某排名前的无人机被传送的次数
   • 某排名前的无人机数量

4. 逐步加入无人机
   对于每个新加入的无人机，计算它对总传送次数的贡献。

代码实现与注释

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

const int N = 150010, B = 550;  // N: 最大数据范围, B: 分块大小
int n, m, t[N], s[N];           // t: 无人机速度, s: 门位置
int mm, S[N], len[N];           // S: 合并后的门间距, len: 每段间距的重复次数

pair<ll, int> bar[N];           // 用于排序: (t_i * S_max, 原始编号)
int pos[N], hav[N];             // pos: 排序后的位置, hav: 暂存数组
int to[551][N];                 // to[i][j]: 对于间距S[i]，无人机j在排序数组中的分界位置

int ind[N], le[N];              // 分块索引: ind[i]表示i所在块号, le[i]表示第i块的左边界

// 分块数据结构1: 维护前缀和(用于计算传送次数)
struct SQRT {
    ll val[N], blv[N];          // val: 单点值, blv: 块内和
    void add(int x, ll v) {
        val[x] += v;
        blv[ind[x]] += v;
    }
    ll ask(int x) {             // 查询前缀[1,x]的和
        ll ans = 0;
        for (int i = 1; i < ind[x]; ++ i) {
            ans += blv[i];      // 完整块的和
        }
        for (int i = le[ind[x]]; i <= x; ++ i) {
            ans += val[i];      // 不完整块的元素
        }
        return ans;
    }
} T1;

// 分块数据结构2: 维护前缀计数(用于计算无人机数量)
struct SQRT2 {
    int val[N], blv[N];         // val: 单点值(0/1), blv: 块内标记
    void add(int x, int v) {
        // 对前缀[1,x]整体加v
        for (int i = 1; i < ind[x]; ++ i) {
            blv[i] += v;        // 完整块打标记
        }
        for (int i = le[ind[x]]; i <= x; ++ i) {
            val[i] += v;        // 不完整块直接加
        }
    }
    int ask(int x) {
        return val[x] + blv[ind[x]];  // 单点值 = 元素值 + 块标记
    }
} T2;

int main() {
    scanf("%d%d", &n, &m);
    
    // 读入无人机速度并预处理分块信息
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &t[i]);
        ind[i] = (i - 1) / B + 1;  // 计算所在块号
        if (ind[i] != ind[i - 1]) {
            le[ind[i]] = i;         // 记录每块左边界
        }
    }
    
    // 读入门位置并计算间距
    for (int i = 1; i <= m; ++ i) {
        scanf("%d", &s[i]);
    }
    for (int i = m; i >= 1; -- i) {
        s[i] = s[i] - s[i - 1];     // 转化为相邻门的间距
    }
    
    // 合并连续相同间距的门
    for (int i = 1; i <= m; ++ i) {
        if (s[i] > S[mm]) {
            S[++mm] = s[i];         // 新的更大间距
        }
        ++ len[mm];                 // 该间距重复次数
    }
    swap(mm, m);  // m现在表示合并后的不同间距数量
    
    // 按 t_i * S_max 对无人机排序
    for (int i = 1; i <= n; ++ i) {
        bar[i] = make_pair(1ll * t[i] * S[m], i);
    }
    sort(bar + 1, bar + n + 1);
    for (int i = 1; i <= n; ++ i) {
        pos[bar[i].second] = i;     // 记录每个无人机的排序后位置
    }
    
    // 预处理to数组: 对于每个间距S[i]，确定每架无人机的分界位置
    for (int i = 1; i < m; ++ i) {
        int pp = 1;  // 指针，在排序数组中移动
        for (int j = 1; j <= n; ++ j) {
            ll val = bar[j].first / S[m];  // 相当于t_id
            int id = bar[j].second;
            // 找到第一个满足 t_pp * S_m > t_id * S_i 的位置
            while (pp <= n && bar[pp] <= make_pair(1ll * val * S[i], id)) {
                ++ pp;
            }
            to[i][id] = pp;  // 记录分界位置
        }
    }
    
    ll ans = 0;
    // 依次加入每架无人机，计算对总传送次数的贡献
    for (int i = 1; i <= n; ++ i) {
        // 处理前m-1段间距
        for (int j = 1; j < m; ++ j) {
            // 对于间距S[j]，该无人机会导致to[j][i]之前的无人机被传送len[j]次
            T1.add(to[j][i], len[j]);
            // 计算新增传送次数 = 传送次数 × 当前无人机数量
            ans += 1ll * len[j] * T2.ask(to[j][i]);
        }
        
        // 处理最后一段间距(最大间距)
        ans += 1ll * len[m] * T2.ask(pos[i]);  // 该无人机传送其他无人机的次数
        T1.add(pos[i], len[m]);                 // 其他无人机传送该无人机的次数
        ans += T1.ask(pos[i]);                  // 累加该无人机被传送的次数
        
        // 将该无人机加入集合
        T2.add(pos[i], 1);
        
        // 输出结果: 总传送次数 = ans - 总门数 × 当前无人机数
        // 因为每个无人机完成比赛时不算传送，要减去这部分
        printf("%lld\n", ans - 1ll * mm * i);
    }
    
    return 0;
}

关键点说明

1. 门间距合并
   连续相同间距的门可以合并处理，因为对于固定间距，无人机的相对顺序不变。

2. 排序依据
   按 $t_i \times S_{\max}$ 排序，因为最大间距决定了无人机的"终极"顺序。

3. 分界位置 to[i][j]
   表示对于间距 $S_i$，无人机 $j$ 会传送掉排序数组中前 to[i][j] - 1 架无人机。

4. 贡献计算
   总传送次数 = ∑(某段间距的传送次数 × 当前无人机数量) + 调整项。

5. 时间复杂度

   • 排序: $O(n \log n)$
   • 预处理: $O(nm)$
   • 查询: $O(n \sqrt{n})$
     总体在给定数据范围内可行。

总结

本题通过排序+分块+预处理的方法，高效地模拟了无人机比赛的传送过程。核心在于将物理过程转化为基于相对顺序的计数问题，利用数据结构快速维护和查询所需信息。