Prefix Equality

题目描述

给定长度为 $N$ 的整数序列 $A = (a_1,\ldots,a_N)$ 和 $B = (b_1,\ldots,b_N)$。
对于 $i=1,...,Q$，以以下格式回答查询。

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

输入格式

输入按如下格式从标准输入提供： $N$ $a_1$ $\ldots$ $a_N$ $b_1$ $\ldots$ $b_N$ $Q$ $x_1$ $y_1$ $\vdots$ $x_Q$ $y_Q$

输出格式

输出 $Q$ 行。第 $i$ 行应包含对第 $i$ 个查询的回答。

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

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$ 输入中的所有值都是整数。注意集合的概念只在于每个值是否被包含。
对于第 $3$ 个查询，$A$ 的前 $2$ 项包含一个 $1$ 和一个 $2$，而 $B$ 的前 $3$ 项包含一个 $1$ 和两个 $2$。然而，这些区间所包含的值的集合均为 $\{ 1,2 \}$，因此相等。
另外，对于第 $6$ 个查询，值出现的顺序不同，但作为集合它们仍然相等。

标签: AtCoder|abc250E

来源

AtCoder|abc250E