配点 : 100 点
問題文
长度相等的数列 a=(a_1,a_2,\dots,a_n) 和 按字典顺序比较 b=(b_1,b_2,\dots,b_n) 关于这个数列,当以下成立时,a 和 按字典顺序比较 b 是 您也可以写相似。 如
- 任何 i=1,2,\dots,n , 当我输入a_i = \max(a_1,a_2,\dots,a_i) 成立时,并且仅在那个时候,b_i = \max(b_1,b_2,\dots,b_i) 成立。
数列 (A_1,A_2,\dots,A_N) 。 对于Q 请回答个查询。查询 i 是整数 L_{i,1}, R_{i,1}, L_{i,2}, R_{i,2} ,序列 (A_{L_{i,1}}, A_{L_{i,1} + 1}, \dots, A_{R_{i,1}}) 和 按字典顺序比较 (A_{L_{i,2}}, A_{L_{i,2} + 1}, \dots, A_{R_{i,2}}) 是否相似。
制約
- 所有输入均为整数
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq L_{i,1} \leq R_{i,1} \leq N
- 1 \leq L_{i,2} \leq R_{i,2} \leq N
- R_{i,1}-L_{i,1} = R_{i,2}-L_{i,2}
入力
输入是按以下格式从标准输入给出的。
N Q
A_1 A_2 \dots A_N
L_{1,1} R_{1,1} L_{1,2} R_{1,2}
L_{2,1} R_{2,1} L_{2,2} R_{2,2}
\vdots
L_{Q,1} R_{Q,1} L_{Q,2} R_{Q,2}
出力
Q 行。i 编号顺序是
第一个 (A_{L_{i,1}}, A_{L_{i,1} + 1}, \dots, A_{R_{i,1}}) 和
按字典顺序比较 (A_{L_{i,2}}, A_{L_{i,2} + 1}, \dots, A_{R_{i,2}}) 如果相似 Yes ,否则
输出 No 。
入力例 1
10 6 3 1 4 1 5 9 2 6 5 3 1 3 3 5 1 5 6 10 1 1 9 9 1 9 1 9 1 3 6 8 5 8 7 10
出力例 1
Yes No Yes Yes No Yes
1 关于第二个查询,
更新为(3,1,4) 和
按字典顺序比较 (4,1,5) 是相似的。因此,Yes 。
2 关于第二个查询,
更新为(3, 1, 4, 1, 5) 和
按字典顺序比较 (9, 2, 6, 5, 3) 不相似。因此,No 。
3 关于第二个查询, 更新为L_{i, 1} = R_{i, 1}, L_{i, 2} = R_{i, 2} 请注意,可能会给出满足 的查询。
4 关于第二个查询, 更新为L_{i, 1} = L_{i, 2}, R_{i, 1} = R_{i, 2} 请注意,可能还会给出满足 的查询。