CF1702C Train and Queries

沿着铁路有编号从 $1$ 到 $10^9$ 的车站。一列特快列车总是沿着由 $n$ 个车站组成的路线行驶，这些车站的编号为 $u_1, u_2, \dots, u_n$，其中 $1 \le u_i \le 10^9$。列车从左到右依次经过这些车站。它从车站 $u_1$ 出发，随后依次停靠 $u_2$、$u_3$，以此类推，终点站为 $u_n$。 列车可能会多次经过同一个车站。也就是说，$u_1, u_2, \dots, u_n$ 中可能存在重复的编号。 你将得到 $k$ 个询问，每个询问包含两个不同的整数 $a_j$ 和 $b_j$（$1 \le a_j, b_j \le 10^9$）。对于每个询问，判断是否可以乘坐列车从编号为 $a_j$ 的车站到编号为 $b_j$ 的车站。 例如，假设列车路线包含 $6$ 个车站，编号为 \[ 3, 7, 1, 5, 1, 4 \] 并给出以下 $3$ 个询问： - $a_1 = 3$，$b_1 = 5$：可以从车站 $3$ 乘车到车站 $5$，路线为 $3, 7, 1, 5$。答案：YES。 - $a_2 = 1$，$b_2 = 7$：不能从车站 $1$ 到车站 $7$，因为列车不能逆向行驶。答案：NO。 - $a_3 = 3$，$b_3 = 10$：不能从车站 $3$ 到车站 $10$，因为车站 $10$ 不在列车路线中。答案：NO。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行为空行。 第二行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \times 10^5, 1 \le k \le 2 \times 10^5$），分别表示列车路线包含的车站数量和询问数量。 第三行包含恰好 $n$ 个整数 $u_1, u_2, \dots, u_n$（$1 \le u_i \le 10^9$）。这些值不一定互不相同。 接下来的 $k$ 行，每行包含两个不同的整数 $a_j$ 和 $b_j$（$1 \le a_j, b_j \le 10^9$），描述第 $j$ 个询问。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$，所有测试用例中 $k$ 的总和也不超过 $2 \times 10^5$。

对于每个测试用例，输出 $k$ 行： - 如果可以乘坐列车从编号为 $a_j$ 的车站到编号为 $b_j$ 的车站，输出 YES； - 否则输出 NO。 YES 和 NO 的大小写均可（例如 yEs、yes、Yes 和 YES 都视为肯定回答）。

第一个测试用例的解释见题目描述。 由 ChatGPT 4.1 翻译