Train and Queries

题意翻译

给你一个长度为 $n (1\le n \le 2 \cdot 10 ^ 5)$ 的数组 $u$。代表所有的火车站。火车只能从左边的站台开到右边的站台。也就是从 $u_1$ 开始，再到 $u_2, \ u_3$，最后到 $u_n$。 现在给你 $k (1\le k \le 2 \cdot 10 ^ 5)$ 个询问，每个包含两个整数 $a_i$ 和 $b_i$，问你是否可以从 $a_i$ 这个站台开始，坐火车到 $b_i$。 比如：$u$ 数组为 $[3,7,1,5,1,4]$，有以下三个询问： - $a_1 = 3, b_1 = 5$。 从 $3$ 号站台坐车到 $5$ 号站台是可能的，有以下路径：$[3,7,1,5]$。 - $a_2 = 1, b_2 = 7$ 没有路径可以从 $1$ 号站坐车做到 $7$ 号站台。 - $a_3 = 3, b_3 = 10$ 没有路径可以从 $3$ 号站台坐车到 $10$ 号站台（$10$ 号根本不存在）。 由 [tzyt](https://www.luogu.com.cn/user/394488) 翻译

题目描述

Along the railroad there are stations indexed from $ 1 $ to $ 10^9 $ . An express train always travels along a route consisting of $ n $ stations with indices $ u_1, u_2, \dots, u_n $ , where ( $ 1 \le u_i \le 10^9 $ ). The train travels along the route from left to right. It starts at station $ u_1 $ , then stops at station $ u_2 $ , then at $ u_3 $ , and so on. Station $ u_n $ — the terminus. It is possible that the train will visit the same station more than once. That is, there may be duplicates among the values $ u_1, u_2, \dots, u_n $ . You are given $ k $ queries, each containing two different integers $ a_j $ and $ b_j $ ( $ 1 \le a_j, b_j \le 10^9 $ ). For each query, determine whether it is possible to travel by train from the station with index $ a_j $ to the station with index $ b_j $ . For example, let the train route consist of $ 6 $ of stations with indices \[ $ 3, 7, 1, 5, 1, 4 $ \] and give $ 3 $ of the following queries: - $ a_1 = 3 $ , $ b_1 = 5 $ It is possible to travel from station $ 3 $ to station $ 5 $ by taking a section of the route consisting of stations \[ $ 3, 7, 1, 5 $ \]. Answer: YES. - $ a_2 = 1 $ , $ b_2 = 7 $ You cannot travel from station $ 1 $ to station $ 7 $ because the train cannot travel in the opposite direction. Answer: NO. - $ a_3 = 3 $ , $ b_3 = 10 $ It is not possible to travel from station $ 3 $ to station $ 10 $ because station $ 10 $ is not part of the train's route. Answer: NO.

输入输出格式

输入格式

The first line of the input contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) —the number of test cases in the test. The descriptions of the test cases follow. The first line of each test case is empty. The second line of each test case contains two integers: $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 10^5 $ ) —the number of stations the train route consists of and the number of queries. The third line of each test case contains exactly $ n $ integers $ u_1, u_2, \dots, u_n $ ( $ 1 \le u_i \le 10^9 $ ). The values $ u_1, u_2, \dots, u_n $ are not necessarily different. The following $ k $ lines contain two different integers $ a_j $ and $ b_j $ ( $ 1 \le a_j, b_j \le 10^9 $ ) describing the query with index $ j $ . It is guaranteed that the sum of $ n $ values over all test cases in the test does not exceed $ 2 \cdot 10^5 $ . Similarly, it is guaranteed that the sum of $ k $ values over all test cases in the test also does not exceed $ 2 \cdot 10^5 $

输出格式

For each test case, output on a separate line: - YES, if you can travel by train from the station with index $ a_j $ to the station with index $ b_j $ - NO otherwise. You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

输入输出样例

输入样例 #1

3
<div class="test-example-line test-example-line-odd test-example-line-1">6 3
3 7 1 5 1 4
3 5
1 7
3 10
<div class="test-example-line test-example-line-even test-example-line-2">3 3
1 2 1
2 1
1 2
4 5
<div class="test-example-line test-example-line-odd test-example-line-3">7 5
2 1 1 1 2 4 4
1 3
1 4
2 1
4 1
1 2

</div></div></div>

输出样例 #1

YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
YES

说明

The first test case is explained in the problem statement.

**题目大意：**
有一列火车沿着铁路线行驶，铁路线上有从1到$10^9$的车站。火车沿特定的路线行驶，路线由$n$个车站组成，车站的编号为$u_1, u_2, \dots, u_n$，其中$1 \le u_i \le 10^9$。火车从左到右行驶，从$u_1$站开始，然后是$u_2$站，依此类推，直到终点站$u_n$。火车可能会多次访问同一个车站，即路线中可能包含重复的车站编号。

给定$k$个询问，每个询问包含两个不同的整数$a_j$和$b_j$（$1 \le a_j, b_j \le 10^9$）。对于每个询问，判断是否可以乘坐火车从$a_j$号车站到$b_j$号车站。

**输入输出数据格式：**
- **输入格式：**
- 第一行包含一个整数$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$），表示火车的路线。
- 接下来的$k$行，每行包含两个整数$a_j$和$b_j$（$1 \le a_j, b_j \le 10^9$），描述一个询问。
- **输出格式：**
- 对于每个测试用例，如果可以从$a_j$号车站乘坐火车到$b_j$号车站，则输出YES，否则输出NO。
- YES和NO的大小写不敏感，即yEs、yes、Yes和YES都会被视为肯定回答。**题目大意：** 有一列火车沿着铁路线行驶，铁路线上有从1到$10^9$的车站。火车沿特定的路线行驶，路线由$n$个车站组成，车站的编号为$u_1, u_2, \dots, u_n$，其中$1 \le u_i \le 10^9$。火车从左到右行驶，从$u_1$站开始，然后是$u_2$站，依此类推，直到终点站$u_n$。火车可能会多次访问同一个车站，即路线中可能包含重复的车站编号。 给定$k$个询问，每个询问包含两个不同的整数$a_j$和$b_j$（$1 \le a_j, b_j \le 10^9$）。对于每个询问，判断是否可以乘坐火车从$a_j$号车站到$b_j$号车站。 **输入输出数据格式：** - **输入格式：** - 第一行包含一个整数$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$），表示火车的路线。 - 接下来的$k$行，每行包含两个整数$a_j$和$b_j$（$1 \le a_j, b_j \le 10^9$），描述一个询问。 - **输出格式：** - 对于每个测试用例，如果可以从$a_j$号车站乘坐火车到$b_j$号车站，则输出YES，否则输出NO。 - YES和NO的大小写不敏感，即yEs、yes、Yes和YES都会被视为肯定回答。