这题主要难在合并一次分段函数，之前没怎么写过，故记之。

首先，注意到比备用车辆快的车肯定不会影响答案，且备用车辆也不会影响比它慢的车的到达时间。于是，把比备用车辆快的车删去，然后每辆车到达每个站的时间是不受询问影响的，可以预处理。

在回答询问的时候，我们让 从 遍历，找到 的车的最大的 ，设为 ，然后令 即可。将每个 上的所有 预先排序，询问时二分即可快速找到 。

观察经过每个调度站后 的变化，可以设 表示经过站 后 会变成啥。容易发现 是一个一次分段函数，每段的斜率是 或 ，有不超过 段。最后的询问，就相当于求 。

根据经典结论，段数为 的分段函数 与段数为 的分段函数 ，它们的复合 段数至多只有 。于是我们可以预先把这 个分段函数合并起来，在查询时只需二分 在哪一段即可。因为暴力合并的时间复杂度是 的，我们需要用分治来合并，即使用 与 合并得到 。这样的时间复杂度就是 的。这也是一种合并信息的经典方法。

代码实现的难点在于：如何合并两个一次分段函数。

我们要求出 长什么样子。首先，取出 定义域上的每一段区间 ，并求出其对应值域区间 。然后，在 的定义域上找到与 有交的那些段，枚举其中一个段，接下来我们只要处理这两段的合并。处理时，把 超出这一段的部分扔掉，然后把将这个 还原成 定义域上的一段区间 ，然后就可以在 中加入一个新的段，其管辖区间是 ，斜率是这两段的斜率相乘，这一段开头的函数值也是容易计算的。

示例代码如下：

struct Node {
	ll l,r,k,b; // 每一段在定义域上的区间，斜率，这一段开头的函数值
	Node(){}
	Node(const ll _l,const ll _r,const ll _k,const ll _b):
		l(_l),r(_r),k(_k),b(_b){}
};
ll Getval(const Node &A,ll x) {
	return A.b + A.k * (x - A.l);
}
inline vector<Node> Merge(const vector<Node> &A,const vector<Node> &B) {
	vector<Node> C;
	int pl = 0,pr = -1;
	for(int i = 0;i < A.size();i++) {
		ll lv = A[i].b,rv = Getval(A[i],A[i].r);
		while(pl < B.size() && B[pl].r < lv) ++pl;
		while(pr + 1 < B.size() && B[pr + 1].l <= rv) ++pr;
		for(int j = pl;j <= pr;j++) {
			ll tl = max(lv,B[j].l),tr = min(rv,B[j].r); // 把 [yl,yr] 超出这一段的部分舍去
			ll o_l,o_r; //将处理后的 [yl,yr] 还原到 f 的定义域上
			if(A[i].k == 0)
				o_l = A[i].l,o_r = A[i].r;
			else {
				o_l = (tl - A[i].b) / A[i].k + A[i].l; 
				o_r = (tr - A[i].b) / A[i].k + A[i].l;
			}
			if(o_l <= o_r)
			C.emplace_back(o_l,o_r,A[i].k * B[j].k,Getval(B[j],tl));
		}
	}
	return C;
}

这题余下的部分比较 trivial ，就不放代码了。