题解：超车换道次数统计

问题分析

本题需模拟 Bajtazar 驾驶跑车超越前方卡车的过程，统计其从右车道换至左车道的次数。核心要点：

1. 卡车特性：前方卡车按距离由近及远编号，速度较慢的卡车会被前方更快的卡车“阻挡”并减速（形成集群）。
2. 换道规则：当 Bajtazar 的车头与卡车尾部对齐时，立即换左车道；一旦可能，立即换回右车道（可能同一时刻多次换道）。
3. 关键计算：需精确计算 Bajtazar 追上卡车的时间、卡车集群合并的时间，以判断换道时机。

关键思路

1. 事件驱动模拟：通过优先队列（大根堆）维护两类关键事件，按时间顺序处理：

   • 追击事件：Bajtazar 追上某辆卡车的时间。
   • 合并事件：后方卡车追上前方卡车并减速合并的时间。

2. 集群管理：用并查集（fa 数组）记录卡车集群的合并状态，每个集群以最前方的卡车为代表，统一管理速度和长度。

3. 分数运算：为避免浮点数精度误差，所有时间、速度、距离的计算均用分数（分子+分母）表示，并重载运算符实现比较和运算。

4. 换道判断：当 Bajtazar 追上某卡车时，若该卡车是当前集群的最前方（未被合并），且其前方无其他卡车阻挡（或前方卡车已被超越），则计数一次换道。

代码解析

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

#define int long long

const int N=1e5+1e3+7;

using ll=__int128;  // 用于分数比较，避免溢出

// 分数结构，存储分子a和分母b
struct Frac {
    int a,b;
    Frac(int _a=0,int _b=1){a=_a,b=_b;}
};

// 事件结构：时间t，事件类型相关参数p和id
struct Event {
    Frac t;
    int p,id;
};

int n;
int fa[N];  // 并查集，管理卡车集群
Frac x[N],d[N],v[N];  // x[i]：卡车i初始距离，d[i]：长度，v[i]：速度（Bajtazar为v[0]）

// 分数加法
Frac operator +(const Frac &a,const Frac &b) {
    if(a.b==b.b) return {a.a+b.a,a.b};
    return {a.a*b.b+b.a*a.b,a.b*b.b};
}

// 分数减法
Frac operator -(const Frac &a,const Frac &b) {
    if(a.b==b.b) return {a.a-b.a,a.b};
    return {a.a*b.b-b.a*a.b,a.b*b.b};
}

// 分数乘法
Frac operator *(const Frac &a,const Frac &b) {
    return {a.a*b.a,a.b*b.b};
}

// 分数除法
Frac operator /(const Frac &a,const Frac &b) {
    return {a.a*b.b,a.b*b.a};
}

// 分数比较（a < b）
bool operator <(const Frac &a,const Frac &b) {
    return (ll)a.a*b.b < (ll)b.a*a.b;  // 交叉相乘比较，避免浮点数误差
}

// 事件优先级：时间早的事件先处理（大根堆中用反向比较）
bool operator <(const Event &a,const Event &b) {
    return b.t < a.t;  // 优先队列默认大根堆，此处实现按t升序
}

// 并查集查找（路径压缩）
int find(int x) {
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入：n为卡车数，D为Bajtazar车长，W/M为其速度v[0]
    cin>>n>>d[0].a>>v[0].a>>v[0].b;
    // 输入卡车信息：x[i]初始距离，d[i]长度，w[i]/m[i]为速度v[i]
    for(int i=1;i<=n;i++)
        cin>>x[i].a>>d[i].a>>v[i].a>>v[i].b;
    
    // 并查集初始化：每辆卡车初始为独立集群
    for(int i=1;i<=n+1;i++)
        fa[i]=i;
    
    priority_queue<Event> q;  // 事件队列（按时间升序处理）
    
    // 1. 添加追击事件：Bajtazar追上第i辆卡车的时间
    // 追击时间 = (x[i] + D) / (V - v[i])，其中D是Bajtazar车长
    for(int i=1;i<=n;i++)
        q.push({(x[i] + d[0]) / (v[0] - v[i]), 0, i});
    
    // 2. 添加合并事件：第i辆卡车追上第i+1辆的时间（若v[i] > v[i+1]）
    // 合并时间 = (x[i+1] - x[i] - d[i+1]) / (v[i] - v[i+1])
    for(int i=1;i<n;i++)
        if(v[i+1] < v[i])  // 只有后方卡车更快才可能合并
            q.push({(x[i+1] - x[i] - d[i+1]) / (v[i] - v[i+1]), i+1, i});
    
    set<int> car;  // 记录当前存在的卡车集群（按编号）
    for(int i=1;i<=n;i++)
        car.insert(i);
    
    int ans=0;  // 换道次数
    
    while(!q.empty()) {
        auto [t, o, e] = q.top();  // 取出最早发生的事件
        q.pop();
        
        if(o == 0) {  // 追击事件：Bajtazar追上卡车e
            // 若卡车e已被合并到其他集群，则忽略
            if(find(e) != e) continue;
            
            // 检查前方是否有未被超越的卡车集群
            int nxt = find(e + 1);  // e的下一个集群
            // 若前方无集群，或前方集群已被Bajtazar超越，则计数换道
            if(nxt == n+1 || !(x[nxt] + v[nxt] * t - d[nxt] < x[0] + v[0] * t))
                ans++;
        } else {  // 合并事件：卡车e追上o（o = e+1），合并为集群o
            // 若o已被合并到其他集群，则忽略
            if(find(o) != o) continue;
            
            // 合并集群：e的父节点设为o
            fa[find(e)] = o;
            // 合并后集群长度为两者之和
            d[o] = d[o] + d[e];
            
            // 从集合中移除e（已合并）
            auto it = car.erase(car.find(e));
            // 若e的前方有集群le，且le速度比o快，则可能发生新的合并
            if(it != car.begin()) {
                auto le = *prev(it);
                if(v[o] < v[le])  // le速度更快，可能追上o
                    q.push({(x[o] - x[le] - d[o]) / (v[le] - v[o]), o, le});
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}

关键步骤详解

1. 分数运算：通过重载运算符实现分数的加减乘除和比较，避免浮点数精度误差，确保时间计算准确。

2. 事件队列：

   • 追击事件：计算 Bajtazar 追上每辆卡车的时间，当追上时判断是否需要换道。
   • 合并事件：当后方卡车速度快于前方时，计算合并时间，合并后更新集群信息并可能生成新的合并事件。

3. 并查集与集合：

   • 并查集 fa 跟踪卡车集群的合并状态，find(x) 找到集群的代表（最前方卡车）。
   • 集合 car 维护当前活跃的集群，便于快速查找前后集群。

4. 换道判断：当 Bajtazar 追上某集群时，若前方无未被超越的集群，则此次追上需要换左车道，计数加 1。

复杂度分析

• 时间复杂度：(O(n \log n))。每个卡车最多生成一次追击事件和一次合并事件，优先队列操作（插入/删除）为 (O(\log n))，整体复杂度适配 (n \leq 10^5)。
• 空间复杂度：(O(n))。存储并查集、事件队列和集合，空间开销可控。

样例验证

以样例 1 为例：

• Bajtazar 速度 (V=1)，卡车速度分别为 (1/4, 1/2, 1/4)。
• 追击事件：计算追上 3 辆卡车的时间分别为 (4/3, 16/3, 44/3)。
• 合并事件：第 2 辆卡车（速度 1/2）会追上第 3 辆（速度 1/4），合并时间为 8。
• 换道判断：第一次追上第 1 辆时前方无阻挡，计数 1；第二次追上第 2 辆时前方无阻挡，计数 2。最终输出 2，与样例一致。

该解法通过事件驱动模拟和集群管理，高效处理卡车合并和换道判断，完美适配题目需求。