AT_abc250_e [ABC250E] Prefix Equality

题目描述

给定两个长度为 $N$ 的整数序列 $A = (a_1, \ldots, a_N)$ 和 $B = (b_1, \ldots, b_N)$。

对于 $i = 1, \ldots, Q$，请回答以下形式的查询：

• 如果 $A$ 的前 $x_i$ 项 $(a_1, \ldots, a_{x_i})$ 所包含的值的集合与 $B$ 的前 $y_i$ 项 $(b_1, \ldots, b_{y_i})$ 所包含的值的集合相等，则输出 Yes，否则输出 No。

输入格式

输入以如下格式从标准输入读入。

$N$
$a_1\ a_2\ \ldots\ a_N$
$b_1\ b_2\ \ldots\ b_N$
$Q$
$x_1\ y_1$
$\vdots$
$x_Q\ y_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

Yes
Yes
Yes
No
No
Yes
No

说明/提示

约束条件

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq 10^9$
• $1 \leq x_i, y_i \leq N$
• 所有输入均为整数。

样例解释 1

请注意，集合只关注每个值是否出现过。在第 $3$ 个查询中，$A$ 的前 $2$ 项包含 $1$ 和 $2$ 各 $1$ 个，$B$ 的前 $3$ 项包含 $1$ 有 $1$ 个，$2$ 有 $2$ 个。但它们所包含的值的集合都是 $\{1,2\}$，因此集合相等。另外，在第 $6$ 个查询中，虽然每个值出现的顺序不同，但作为集合它们依然相等。

由 ChatGPT 4.1 翻译