题解：马拉松大会 2（Marathon Race 2）

核心结论：通过排序+前缀和预处理球的位置，枚举4种最优路径（覆盖所有最短时间可能），对每个查询 $O(1)$ 计算最小时间并与 $T_j$ 比较，即可判断是否完赛。

一、关键观察与时间计算逻辑

1. 最优路径的核心性质

理惠的行动分为三部分：从起点 $S$ 到第一个球、收集所有球、从最后一个球到终点 $G$。收集所有球的最优路径必然是在球位置的左右端点之间往返（贪心思想），因为绕路会增加距离和时间。

设球的位置排序后为 $x_1 \leq x_2 \leq \dots \leq x_N$，定义左右端点 $L = x_1$、$R = x_N$（多个球在同一位置不影响，排序后仍为连续相同值）。

2. 时间计算拆解

总时间 = 移动时间 + 拿球时间（固定为 $N$ 秒，每个球1秒）。

移动时间的核心规律：拿着 $k$ 个球跑1米耗时 $k+1$ 秒，收集第 $i$ 个球后持球数为 $i$，因此：

• 从第 $a$ 个球到第 $b$ 个球（$a < b$）的移动时间 = $\sum_{k=a}^{b-1} (k+1) \times |x_{k+1} - x_k| = \sum_{k=a}^{b-1} (k+1) \times (x_{k+1} - x_k)$（排序后单调不减，绝对值可去掉）。

3. 4种候选最优路径

所有最优路径仅需考虑以下4种（覆盖从 $S$ 出发、到 $G$ 结束的所有最短可能）：

1. $S \to L \to R \to G$
2. $S \to R \to L \to G$
3. $S \to L \to R \to L \to G$（仅当 $G$ 在 $[L, R]$ 左侧时可能更优）
4. $S \to R \to L \to R \to G$（仅当 $G$ 在 $[L, R]$ 右侧时可能更优）

二、预处理步骤（$O(N \log N)$）

1. 排序与端点计算

• 对所有球的位置 $X$ 排序，得到 $x_1 \leq x_2 \leq \dots \leq x_N$。
• 计算左右端点 $L = x_1$、$R = x_N$。

2. 前缀和预处理

定义两个前缀和数组，用于快速计算移动时间：

• $sum1[i]$：前 $i$ 个球之间的移动时间（从 $x_1$ 到 $x_i$），即 $\sum_{k=1}^{i-1} (k+1) \times (x_{k+1} - x_k)$。
• $sum2[i]$：前 $i$ 个球之间的“反向系数”和，即 $\sum_{k=1}^{i-1} (N - k + 1) \times (x_{k+1} - x_k)$（用于计算从 $R$ 到 $L$ 的移动时间）。

预处理公式：

• $sum1[1] = 0$；$sum1[i] = sum1[i-1] + i \times (x_i - x_{i-1})$（$i \geq 2$）。
• $sum2[1] = 0$；$sum2[i] = sum2[i-1] + (N - i + 2) \times (x_i - x_{i-1})$（$i \geq 2$）。

最终：

• 从 $L$ 到 $R$ 的移动时间 = $sum1[N]$。
• 从 $R$ 到 $L$ 的移动时间 = $sum2[N]$。

三、查询处理（$O(1)$ per query）

对每个查询 $(S_j, G_j, T_j)$，计算4种路径的总时间，若最小时间 $\leq T_j$ 则输出 Yes，否则 No。

1. 路径时间计算细节

设：

• $t_{S\to L} = (0 + 1) \times |S - L|$（从起点出发，持球数0，跑1米耗时1秒）。
• $t_{S\to R} = 1 \times |S - R|$（同上）。
• $t_{R\to G} = (N + 1) \times |R - G|$（收集完所有球，持球数 $N$，跑1米耗时 $N+1$ 秒）。
• $t_{L\to G} = (N + 1) \times |L - G|$（同上）。
• $t_{L\to R} = sum1[N]$（从 $L$ 到 $R$ 的移动时间）。
• $t_{R\to L} = sum2[N]$（从 $R$ 到 $L$ 的移动时间）。

4种路径的总时间：

1. 路径1：$t_{S\to L} + t_{L\to R} + t_{R\to G} + N$。
2. 路径2：$t_{S\to R} + t_{R\to L} + t_{L\to G} + N$。
3. 路径3：$t_{S\to L} + t_{L\to R} + t_{R\to L} + t_{L\to G} + N$（往返 $L-R-L$）。
4. 路径4：$t_{S\to R} + t_{R\to L} + t_{L\to R} + t_{R\to G} + N$（往返 $R-L-R$）。

2. 特殊情况处理

• 当 $N=0$：无需拿球，总时间 = $|S - G|$（但题目中 $N \geq 1$，可忽略）。
• 当 $L = R$（所有球在同一位置）：$t_{L\to R} = t_{R\to L} = 0$，路径简化为 $S \to L \to G$，总时间 = $|S-L| + |L-G| \times (N+1) + N$。

四、代码实现

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int L = Integer.parseInt(line[1]);
        
        int[] X = new int[N];
        line = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            X[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(X);
        
        // 预处理前缀和 sum1 和 sum2
        long[] sum1 = new long[N + 1]; // sum1[i]：x1到xi的移动时间
        long[] sum2 = new long[N + 1]; // sum2[i]：xN到xi的反向移动时间（从右到左）
        for (int i = 2; i <= N; i++) {
            long dist = X[i - 1] - X[i - 2];
            sum1[i] = sum1[i - 1] + (long) i * dist; // 第i-1步持球数为i-1，耗时(i-1)+1 = i
            sum2[i] = sum2[i - 1] + (long) (N - i + 2) * dist; // 反向时第i-1步持球数为N - (i-1)，耗时(N -i +1)+1 = N -i +2
        }
        long t_LR = sum1[N]; // L到R的时间
        long t_RL = sum2[N]; // R到L的时间
        int left = X[0];
        int right = X[N - 1];
        
        int Q = Integer.parseInt(br.readLine());
        while (Q-- > 0) {
            line = br.readLine().split(" ");
            int S = Integer.parseInt(line[0]);
            int G = Integer.parseInt(line[1]);
            long T = Long.parseLong(line[2]);
            
            // 计算4种路径的时间
            long t1 = (long) Math.abs(S - left) + t_LR + (long) (N + 1) * Math.abs(right - G) + N;
            long t2 = (long) Math.abs(S - right) + t_RL + (long) (N + 1) * Math.abs(left - G) + N;
            long t3 = (long) Math.abs(S - left) + t_LR + t_RL + (long) (N + 1) * Math.abs(left - G) + N;
            long t4 = (long) Math.abs(S - right) + t_RL + t_LR + (long) (N + 1) * Math.abs(right - G) + N;
            
            long minTime = Math.min(Math.min(t1, t2), Math.min(t3, t4));
            if (minTime <= T) {
                bw.write("Yes\n");
            } else {
                bw.write("No\n");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

五、复杂度分析

• 预处理：排序 $O(N \log N)$ + 前缀和计算 $O(N)$，总 $O(N \log N)$。
• 查询：每个查询计算4种路径时间，$O(1)$ 处理，总 $O(Q)$。
• 整体复杂度 $O(N \log N + Q)$，适配 $N, Q \leq 5 \times 10^5$ 的数据规模。