分数: 333 分
问题陈述
高桥是一名登山向导。在某一个山区, N 山间小屋一字排开。的 i左起第一个山间小屋(以下简称小屋 i) 的海拔高度为 A_i 米。
相邻山间小屋之间,仅在高差较小时才保留步道。具体来说,对于小屋 i 和小屋 i+1,如果高程的绝对差最多为 K (即 |A_i - A_{i+1}| \leq K),它们之间有一条小路,可以直接在它们之间移动。如果高程的绝对差大于 K,没有踪迹,无法直接在它们之间旅行。不相邻的山间小屋之间没有步道。
通过遵循一系列路径可以相互到达的最大一组山间小屋称为 区域。由于小径仅存在于相邻小屋之间,因此属于每个区域的小屋编号始终形成连续的间隔。形式上,区域是一个连续的区间 [l, r] (1 \leq l \leq r \leq N)满足以下两个条件的小屋编号:
- 区间内所有相邻小屋之间都有一条小路。也就是说,对于所有整数 i 这样 l \leq i \leq r-1, |A_i - A_{i+1}| \leq K 成立。 (当 l = r,自动满足此条件。)
- 间隔最大。也就是说,如果 l \geq 2 然后 |A_{l-1} - A_l| > K,如果 r \leq N-1 然后 |A_r - A_{r+1}| > K.
每个 N 山间小屋属于一个区域。
高桥想回答 Q 问题。对于 j第题,判断是否是小屋 L_j 和小屋 R_j 属于同一区域。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
- 所有输入值均为整数。
输入
N K Q A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 第一行包含三个空格分隔的整数: N 代表山间小屋的数量, K 表示路径存在的最大高程差(当高程差最大时,路径存在 K),以及 Q 代表问题数量。
- 第二行包含空格分隔的整数 A_1, A_2, \ldots, A_N 从左到右代表山间小屋的海拔。
- 以下 Q 行每行包含一个问题。
- 的 j- 这些行( (2 + j)-整个输入的第行)包含空格分隔的小屋编号 L_j 和 R_j 为 j- 第一个问题。
输出
输出 Q 行。上 j第行,打印 Yes 如果小屋 L_j 和小屋 R_j 属于同一区域 j第一个问题,以及 No 否则。
示例输入 1
6 3 3 10 13 15 25 27 26 1 3 2 5 4 6
示例输出 1
Yes No Yes
示例输入 2
9 5 5 100 102 110 112 111 105 103 200 198 1 2 1 3 3 5 6 9 8 9
示例输出 2
Yes No Yes No Yes
示例输入 3
12 4 6 50 52 54 56 100 98 96 94 92 90 50 52 1 4 1 5 5 10 10 11 11 12 3 12
示例输出 3
Yes No Yes No Yes No