103675: [Atcoder]ABC367 F - Rearrange Query

Problem Statement

You are given sequences of positive integers of length $N$: $A=(A_1,A_2,\ldots,A_N)$ and $B=(B_1,B_2,\ldots,B_N)$.

You are given $Q$ queries to process in order. The $i$-th query is explained below.

• You are given positive integers $l_i,r_i,L_i,R_i$. Print Yes if it is possible to rearrange the subsequence $(A_{l_i},A_{l_i+1},\ldots,A_{r_i})$ to match the subsequence $(B_{L_i},B_{L_i+1},\ldots,B_{R_i})$, and No otherwise.

Constraints

• $ 1\leq N,Q\leq 2\times 10^5$
• $ 1\leq A_i,B_i\leq N$
• $ 1\leq l_i \leq r_i\leq N$
• $ 1\leq L_i \leq R_i\leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$
$l_1$ $r_1$ $L_1$ $R_1$
$l_2$ $r_2$ $L_2$ $R_2$
$\vdots$
$l_Q$ $r_Q$ $L_Q$ $R_Q$

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

5 4
1 2 3 2 4
2 3 1 4 2
1 3 1 3
1 2 3 5
1 4 2 5
1 5 1 5

Sample Output 1

Yes
No
No
Yes

• For the 1st query, it is possible to rearrange $(1,2,3)$ to match $(2,3,1)$. Hence, we print Yes.
• For the 2nd query, it is impossible to rearrange $(1,2)$ in any way to match $(1,4,2)$. Hence, we print No.
• For the 3rd query, it is impossible to rearrange $(1,2,3,2)$ in any way to match $(3,1,4,2)$. Hence, we print No.
• For the 4th query, it is possible to rearrange $(1,2,3,2,4)$ to match $(2,3,1,4,2)$. Hence, we print Yes.

Sample Input 2

4 4
4 4 4 4
4 4 4 4
1 2 2 3
3 3 1 1
1 3 1 4
1 4 2 3

Sample Output 2

Yes
Yes
No
No

问题陈述

给定长度为$N$的正整数序列：$A=(A_1,A_2,\ldots,A_N)$和$B=(B_1,B_2,\ldots,B_N)$。

按顺序处理给定的$Q$个查询。第$i$个查询如下所述。

• 给定正整数$l_i,r_i,L_i,R_i$。如果可以将子序列$(A_{l_i},A_{l_i+1},\ldots,A_{r_i})$重新排列以匹配子序列$(B_{L_i},B_{L_i+1},\ldots,B_{R_i})$，则打印Yes，否则打印No。

约束条件

• $ 1\leq N,Q\leq 2\times 10^5$
• $ 1\leq A_i,B_i\leq N$
• $ 1\leq l_i \leq r_i\leq N$
• $ 1\leq L_i \leq R_i\leq N$
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$
$l_1$ $r_1$ $L_1$ $R_1$
$l_2$ $r_2$ $L_2$ $R_2$
$\vdots$
$l_Q$ $r_Q$ $L_Q$ $R_Q$

输出

打印$Q$行。第$i$行应包含对第$i$个查询的答案。

示例输入1

5 4
1 2 3 2 4
2 3 1 4 2
1 3 1 3
1 2 3 5
1 4 2 5
1 5 1 5

示例输出1

Yes
No
No
Yes

• 对于第1个查询，可以将$(1,2,3)$重新排列以匹配$(2,3,1)$。因此，我们打印Yes。
• 对于第2个查询，无法以任何方式重新排列$(1,2)$以匹配$(1,4,2)$。因此，我们打印No。
• 对于第3个查询，无法以任何方式重新排列$(1,2,3,2)$以匹配$(3,1,4,2)$。因此，我们打印No。
• 对于第4个查询，可以将$(1,2,3,2,4)$重新排列以匹配$(2,3,1,4,2)$。因此，我们打印Yes。

示例输入2

4 4
4 4 4 4
4 4 4 4
1 2 2 3
3 3 1 1
1 3 1 4
1 4 2 3

示例输出2

Yes
Yes
No
No