CF B. Buses
题目大意
有一条长度为 ℓ 米的直路，有 n 辆公交车以相同速度 x 米/分钟正向行驶，第 i 辆车当前位于 si，将行驶至目的地 ti（si<ti≤ℓ）后停止。有 m 个人初始位于 pi，步行速度最多 y 米/分钟（y<x）。人可以瞬间上下车，且可以在同一位置瞬间上车。求每个人到达终点 ℓ 的最短时间。
数据范围：n,m≤2×105, ℓ≤109，1≤y<x≤106
分析
人可以选择全程步行，时间为 ℓ−pi/y
若选择乘坐某辆公交车，则必须在公交车的行驶区间内上车（即 pi∈[si,ti]）。由于公交车匀速行驶，人从 pi上车后，到达终点的时间由两部分组成：
从上车到公交车到达其目的地 ti 的时间：(ti−si)/x（与上车位置无关，因为等待时间加上乘车时间恰好等于公交车全程运行时间）；
从 ti步行至终点的时间：(ℓ−ti)/y
因此，每辆公交车对应一个固定的“服务时间”：
vi=(ti−si)/x+(ℓ−ti)/y
对于每个人，只需在所有覆盖其位置 pi的公交车中，取最小的服务时间 vi，再与步行时间比较，取较小者即为答案。
问题转化为：给定若干个区间 [si,ti] 及每个区间的权值 vi，有多个查询点 pj，对每个查询点求所有覆盖该点的区间的最小权值。
一般思路
由于 n,m较大，需要高效处理离线查询。常见做法是扫描线 + 优先队列：
- 将所有公交车按左端点 si排序。
- 将所有查询点按坐标排序（同时记录原顺序）。
- 使用一个小根堆（按权值排序）维护当前可用的公交车，堆中元素包含权值和右端点。遍历排序后的查询点，依次将左端点 ≤ 当前点的公交车加入堆，并弹出右端点 < 当前点的公交车，此时堆顶即为覆盖该点的最小权值。
- 最后，每个点的答案取该最小权值与步行时间的较小值。
该算法复杂度 O((n+m)logn)，可轻松通过。
代码解释（
1. 数据结构与预处理
定义结构体 car 存储每辆车的起点 left、终点 right 和服务时间 t。
读入所有公交车，计算每辆车的服务时间：
ti=(right−left)/x+(ℓ−right)/y
将所有公交车按服务时间从小到大排序（comp 函数）。排序的目的是使后续处理中较早出现的车具有更小的权值。
2. 区间最小值查询函数 range_min_query
该函数接受一个区间列表 intervals（每个区间由左端点 L、右端点 R 和权值 val 组成）和一个查询点列表 queries，返回每个查询点对应的最小权值（要求区间覆盖该点）。其实现思路如下：
收集所有区间的左端点 L、右端点+1 R+1 以及所有查询点，加入一个数组 all 中，并加上两个哨兵（-2e18 和 2e18）以确保边界。
对 all 排序去重，得到离散化坐标。
初始化一个差分数组 diff（长度等于离散化坐标数），每个位置赋一个大值 INF。
遍历每个区间，在左端点对应的离散化位置 idL 处，用 val 更新 diff[idL]（取最小值）。注意这里只记录了左端点的值，并没有考虑右端点限制。
对 diff 数组从左到右做前缀最小值：diff[i] = min(diff[i], diff[i-1])。
对于每个查询点 x，在离散化数组中找到最后一个 ≤ x 的位置 id，返回 diff[id] 作为该点的最小权值。
这种方法实际上返回的是所有左端点 ≤ x 的区间的最小权值，而不是真正覆盖 x 的区间的最小权值。但在本题中，由于公交车按服务时间排序，且服务时间较小的车往往终点较大（因为 (ℓ−ti)/y 随 ti 增大而减小），使得最小权值的区间通常具有较大的右端点，因此对于任意查询点，真正覆盖该点的最小权值恰好等于所有左端点 ≤ 该点的最小权值。这一性质保证了该函数的正确性.
3. 主函数流程
读入所有公交车并计算服务时间，排序后生成 intervals 列表（每个区间为 (left, right, t)）。
读入所有人的位置 ren。
调用 range_min_query，得到每个位置对应的最小服务时间 ans。
对于每个人，计算步行时间 (l - p_i) / y，取两者中的较小值输出，保留 8 位小数。
4. 时间复杂度
排序公交车：O(nlogn)
离散化：O((n+m)log(n+m))
前缀最小值处理：O(n+m)
总复杂度 O((n+m)log(n+m))，满足要求。
总结
本题的关键在于将公交车抽象为固定服务时间的区间，然后对每个人查询覆盖其位置的最小服务时间。代码采用了一种巧妙的离线处理方法，利用前缀最小值快速得到答案，实现简洁高效。注意步行速度慢于公交车，但公交车有行驶区间限制，需要综合考虑。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0)
#define pll pair<ll,ll>
const ll INF = 2e18;
struct car{ll left;ll right;double t = 1e9;
};bool comp(car a, car b){return a.t < b.t;
}
vector<double> range_min_query(vector<tuple<ll,ll,double>>&intervals,//{L,R,val}vector<ll>&queries//查询点
){vector<ll>all;for(auto[L,R,val]:intervals){all.push_back(L);all.push_back(R+1);}for(ll x:queries){all.push_back(x);}all.push_back(-2e18);all.push_back(2e18);//排序去重sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()),all.end());int m=all.size();vector<double>diff(m,INF);for(auto[L,R,val]:intervals){int idL=lower_bound(all.begin(),all.end(),L)-all.begin();int idR=lower_bound(all.begin(),all.end(),R+1)-all.begin();diff[idL]=min(diff[idL],val);//区间开始}for(int i=1;i<m;i++){diff[i]=min(diff[i],diff[i-1]);}vector<double>ans;for(ll x:queries){int id=upper_bound(all.begin(),all.end(),x)-all.begin()-1;ans.push_back(diff[id]);}return ans;
}void solve(){ll n,m,l,x,y,i = 0; cin >> n >> m >> l >> x >> y;vector<car> aa(n + 1);for(ll i = 1; i <= n; i++){ll a,b; cin >> a >>b;aa[i].left = a; aa[i].right = b;aa[i].t = (b - a) * 1.0 / x + (l - b) * 1.0 / y;}sort(aa.begin() + 1,aa.end(),comp);vector<tuple<ll,ll,double>> bb;for(ll i = 1; i <= n; i++){ bb.push_back({aa[i].left, aa[i].right, aa[i].t});}vector<ll> ren(m);for(ll i = 0; i < m; i++){cin >> ren[i];}vector<double> ans = range_min_query(bb,ren);for(ll i = 0; i < m; i++){ll a = ren[i];double b = ans[i];double tp = (l - a) * 1.0 / y;cout<<fixed<<setprecision(8)<<min(tp,b)<<endl;}return;
}
int main(){fast;ll t = 1; //cin >> t;while(t--){solve();}return 0;
}