环形路线 - 题目

Little Cyan Fish 是杯子宇宙中 H 市的国王。在 H 市，有一条长度为 $L$ 的环形路线。路线上有 $L$ 个车站，编号为 $0, \dots, L-1$，按逆时针方向排列。车站 $(p+1) \pmod L$ 位于从车站 $p$ 沿逆时针方向走单位距离到达的位置。

一辆公交车在时间 $0$ 从车站 $x$ 出发，以 $1$ 的恒定速度沿该环形路线逆时针行驶，循环往复。公交车很小，因此在任何时刻车上最多只能有一名乘客。

现在有 $n$ 个人想要乘坐公交车。第 $i$ 个人想要从车站 $s_i$ 前往目的地车站 $t_i$。乘客可以在公交车到达其起始车站时上车，并必须留在车上直到到达目的地。他们也可以选择不上车，等待公交车在未来的循环中再次到达。

Little Cyan Fish 想知道，从时间 $0$ 开始，将所有人运送到各自目的地所需的最短时间是多少？我们假设上下车是瞬间完成的，不需要任何额外时间。

请回答关于不同起点 $x$ 所需最短时间的 $q$ 个询问。

输入文件包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $L$ ($1 \le n \le 2 \times 10^5, 2 \le L \le 10^9$)。

接下来的 $n$ 行描述了 $n$ 个人的旅行计划。第 $i$ 行包含两个整数 $s_i$ 和 $t_i$ ($0 \le s_i, t_i < L, s_i \neq t_i$)，表示第 $i$ 个人的起点和终点。

下一行包含一个整数 $q$ ($1 \le q \le 10^6$)。

接下来的 $q$ 行描述了询问。第 $i$ 行包含一个整数 $x_i$，表示公交车在时间 $0$ 时的位置。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$，所有测试用例中 $q$ 的总和不超过 $10^6$。

对于每个测试用例，输出 $q$ 行。第 $i$ 行应包含一个整数，表示起点为 $x_i$ 时的答案。

3
2 10
3 7
8 0
4
1
3
5
9
4 4
0 2
2 0
1 3
3 1
1
0
3 1000000000
0 999999999
0 999999999
0 999999999
1
1

QOJ.ac