AT_utpc2024_a.Array Similarity

对于长度相等的数列 $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}})$ 是否相似。

输入按以下格式从标准输入读入：

$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

对于第 $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}$ 的询问。

数据范围

• 所有输入均为整数
• $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}$

由 ChatGPT 5 翻译