← 返回题目列表

Codeforces · 1702/C

C. 训练和查询

中文机器翻译题面 查看原题

铁路沿线有索引从 $$$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$$$ 的车站。

例如,假设火车路线由索引为 [$$$3, 7, 1, 5, 1, 4$$$] 的车站 $$$6$$$ 组成,并给出以下查询的 $$$3$$$:

- $$$a_1 = 3$$$, $$$b_1 = 5$$$可以通过走由车站 [$$$3, 7, 1, 5$$$] 组成的一段路线从车站 $$$3$$$ 前往车站 $$$5$$$。答案:是的。
- $$$a_2 = 1$$$, $$$b_2 = 7$$$您无法从车站 $$$1$$$ 前往车站 $$$7$$$,因为火车无法沿相反方向行驶。答案:不。
- $$$a_3 = 3$$$,$$$b_3 = 10$$$无法从车站 $$$3$$$ 前往车站 $$$10$$$,因为车站 $$$10$$$ 不是火车路线的一部分。答案:不。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。

测试用例的描述如下。

每个测试用例的第一行是空的。

每个测试用例的第二行包含两个整数:$$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 10^5$$$) - 火车路线包含的车站数量和查询数量。

每个测试用例的第三行恰好包含 $$$n$$$ 整数 $$$u_1, u_2, \dots, u_n$$$ ($$$1 \le u_i \le 10^9$$$)。值 $$$u_1、u_2、\dots、u_n$$$ 不一定不同。

以下 $$$k$$$ 行包含两个不同的整数 $$$a_j$$$ 和 $$$b_j$$$ ($$$1 \le a_j, b_j \le 10^9$$$) 描述索引 $$$j$$$ 的查询。

保证测试中所有测试用例的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。同样,保证测试中所有测试用例的 $$$k$$$ 值的总和也不超过 $$$2 \cdot 10^5$$$

输出

对于每个测试用例,在单独的行上输出:

- 是,如果您可以乘坐火车从索引为 $$$a_j$$$ 的车站前往索引为 $$$b_j$$$ 的车站
- 否则不。

在任何情况下都可以输出 YES 和 NO(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应)。

示例

输入 #1

3
6 3
3 7 1 5 1 4
3 5
1 7
3 10
3 3
1 2 1
2 1
1 2
4 5
7 5
2 1 1 1 2 4 4
1 3
1 4
2 1
4 1
1 2

输出 #1

YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
YES

注意

第一个测试用例在问题陈述中进行了解释。