← 返回题目列表

AtCoder · utpc2024_a

A. 数组相似度

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

配点 : 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} 请注意,可能还会给出满足 的查询。