A - Array Similarity Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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} を満たすクエリも与えられることがある点に注意してください。