AT_joi2025ho_c ミ・テレフェリコ (Mi Teleférico)

玻利维亚首都拉巴斯是著名的旅游胜地，其中的空中索道 Mi Teleférico 也很有名。你正在拉巴斯观光，并想尽可能多地游览景点。在本题中，我们考虑如下简化的情形。 拉巴斯共有 $N$ 个空中索道车站，按照海拔高度递增的顺序编号为 $1$ 到 $N$。共有 $M$ 条**单向**索道线路，编号为 $1$ 到 $M$。有 $P$ 个空中索道公司，编号为 $1$ 到 $P$。每条线路由一个公司管理。第 $i$ 条线路（$1 \leq i \leq M$）从车站 $A_i$ 通往车站 $B_i$，由公司 $C_i$ 负责运营。注意，线路总是从低海拔车站开往高海拔车站，即 $A_i < B_i$ 恒成立。 为了方便出行，拉巴斯交通局发售了不限次数的乘车通票。每张通票包含两个整数 $l, r$，满足 $1 \leq l \leq r \leq P$。持有该通票的人可以乘坐任意由公司 $l, l+1, \dots, r$ 管理的线路。换句话说，对于 $1 \leq i \leq M$，当 $l \leq C_i \leq r$ 时，持票人可以乘坐第 $i$ 条线路。每张通票可以用于多条符合条件的线路。我们记通票 $(l, r)$ 表示这种乘车通票。 现在有 $Q$ 位游客，编号为 $1$ 到 $Q$。第 $j$ 位游客持有通票 $(L_j, R_j)$ 并拥有 $X_j$ 博利瓦诺现金。 每位游客的目标是，确保用自己目前拥有的通票，仅通过可乘坐的线路，从车站 $1$ 出发，能够到达每一个车站。对于第 $j$ 位游客（$1 \leq j \leq Q$），可以按如下流程将手头的通票兑换一次，以达成目标： 1. 他或她选择两个整数 $l', r'$，使 $1 \leq l' \leq r' \leq P$。 2. 以 $|L_j - l'| + |R_j - r'|$ 博利瓦诺的手续费，将通票 $(L_j, R_j)$ 换为通票 $(l', r')$。 请你判定对于每一位游客，能否在其手头现金范围内，实现从 $1$ 号车站出发，使用可以乘坐的线路到达全部车站的目标。 编写程序，根据给定的车站、线路和游客信息，判断每位游客能否在规定现金内达成目标。 ---

从标准输入依次读取以下数据： > $N\ M\ P$ > $A_1\ B_1\ C_1$ > $A_2\ B_2\ C_2$ > $\vdots$ > $A_M\ B_M\ C_M$ > $Q$ > $L_1\ R_1\ X_1$ > $L_2\ R_2\ X_2$ > $\vdots$ > $L_Q\ R_Q\ X_Q$

向标准输出输出 $Q$ 行，第 $j$ 行（$1 \leq j \leq Q$）输出 `Yes`，如果第 $j$ 位游客可以实现目标，否则输出 `No`。 ---

### 子任务 1.（$7$ 分）$N \leq 50$，$M \leq 50$，$Q \leq 50$，并且 $X_j = 0$（$1 \leq j \leq Q$）。 2.（$8$ 分）$P \leq 10$。 3.（$11$ 分）$P \leq 100$。 4.（$23$ 分）$P \leq 300\,000$，$X_j = 0$（$1 \leq j \leq Q$）。 5.（$9$ 分）$P \leq 300\,000$。 6.（$22$ 分）$N \leq 8\,000$，$M \leq 8\,000$。 7.（$20$ 分）无额外限制。 --- ### 样例解释 1 首先，第 $1$ 位游客初始持有通票 $(3, 7)$ 和 $0$ 博利瓦诺现金。他不需要换票即可达成目标。因为此票能乘坐下列四条线路：第 $1, 2, 3, 4$ 条，并且可以按以下方式从车站 $1$ 到达所有其它车站： - 通过线路 $3$ 可达 $1 \rightarrow 2$。 - 通过线路 $1, 4$ 顺序可达 $1 \rightarrow 2 \rightarrow 3$。 - 通过线路 $3, 2$ 顺序可达 $1 \rightarrow 2 \rightarrow 4$。 因此，第 $1$ 行输出 `Yes`。 接着，第 $2$ 位游客初始持有通票 $(5, 6)$ 和 $0$ 博利瓦诺现金。但此票只能乘坐第 $3, 4$ 两条线路，无法从 $1$ 号车站到达 $4$ 号车站，也没有现金换票，因此输出 `No`。 同理，第 $3$ 位游客无法达成目标，第 $4$ 位游客可以达成目标。所以第 $3$ 行输出 `No`，第 $4$ 行输出 `Yes`。 该样例满足所有子任务的约束条件。 --- ### 样例解释 2 车站和线路信息与样例输入 $1$ 相同。 第 $1$ 位游客初始持有通票 $(5, 6)$ 和 $10$ 博利瓦诺现金。他可以通过以下方式达成目标： 1. 选择 $l' = 1, r' = 5$。 2. 花费 $|5 - 1| + |6 - 5| = 5$ 博利瓦诺，将通票换为 $(1, 5)$。 所以第 $1$ 行输出 `Yes`。 第 $2$ 位游客初始持有通票 $(3, 4)$ 和 $1$ 博利瓦诺现金，无法通过任何换票方式达成目标。 第 $3$ 位游客可以达成目标，因此第 $3$ 行输出 `Yes`。 这样，该输入满足子任务 $2, 3, 5, 6, 7$ 的约束。 --- ### 样例解释 3 对于这些线路，不可能从 $1$ 号车站到达 $3$ 号车站，因此无论通票如何，游客都无法达成目的。 此样例满足子任务 $6, 7$ 的约束。 --- ### 样例解释 4 此样例满足子任务 $5, 6, 7$ 的约束。 ### 约束条件 - $2 \leq N \leq 300\,000$。 - $1 \leq M \leq 300\,000$。 - $1 \leq P \leq 10^9$。 - $1 \leq A_i < B_i \leq N$（$1 \leq i \leq M$）。 - $1 \leq C_i \leq P$（$1 \leq i \leq M$）。 - $1 \leq Q \leq 400\,000$。 - $1 \leq L_j \leq R_j \leq P$（$1 \leq j \leq Q$）。 - $0 \leq X_j \leq 10^9$（$1 \leq j \leq Q$）。 - 所有输入数据均为整数。 由 ChatGPT 5 翻译