102504: [AtCoder]ABC250 E - Prefix Equality
Description
Score : $500$ points
Problem Statement
You are given integer sequences $A = (a_1,\ldots,a_N)$ and $B = (b_1,\ldots,b_N)$, each of length $N$.
For $i=1,...,Q$, answer the query in the following format.
- If the set of values contained in the first $x_i$ terms of $A$, $(a_1,\ldots,a_{x_i})$, and the set of values contained in the first $y_i$ terms of $B$, $(b_1,\ldots,b_{y_i})$, are equal, then print
Yes
; otherwise, printNo
.
Constraints
- $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$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $a_1$ $\ldots$ $a_N$ $b_1$ $\ldots$ $b_N$ $Q$ $x_1$ $y_1$ $\vdots$ $x_Q$ $y_Q$
Output
Print $Q$ lines. The $i$-th line should contain the response to the $i$-th query.
Sample Input 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
Sample Output 1
Yes Yes Yes No No Yes No
Note that sets are a concept where it matters only whether each value is contained or not.
For the $3$-rd query, the first $2$ terms of $A$ contain one $1$ and one $2$, while the first $3$ terms of $B$ contain one $1$ and two $2$'s. However, the sets of values contained in the segments are both $\{ 1,2 \}$, which are equal.
Also, for the $6$-th query, the values appear in different orders, but they are still equal as sets.
Input
题意翻译
给定两个长为 $N$ 的数列 $A,B$ 与 $Q$ 次询问,每次询问给出 $x_i,y_i$,求出 $A$ 的前 $x_i$ 项去重后是否与 $B$ 的前 $y_i$ 项相同。Output
问题描述
给你两个整数序列 $A = (a_1,\ldots,a_N)$ 和 $B = (b_1,\ldots,b_N)$,每个长度为 $N$。
对于 $i=1,...,Q$,以以下格式回答查询。
- 如果集合 $A$ 的前 $x_i$ 项 $(a_1,\ldots,a_{x_i})$ 和集合 $B$ 的前 $y_i$ 项 $(b_1,\ldots,b_{y_i})$ 相等,则打印
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$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出:
$N$ $a_1$ $\ldots$ $a_N$ $b_1$ $\ldots$ $b_N$ $Q$ $x_1$ $y_1$ $\vdots$ $x_Q$ $y_Q$
输出
打印 $Q$ 行。第 $i$ 行应包含对第 $i$ 个查询的响应。
样例输入 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
注意集合是一个只关心每个值是否包含的概念。
对于第 $3$ 个查询,$A$ 的前 $2$ 项包含一个 $1$ 和一个 $2$,而 $B$ 的前 $3$ 项包含一个 $1$ 和两个 $2$。但是,这两个段包含的值的集合都是 $\{ 1,2 \}$,它们是相等的。
同样,对于第 $6$ 个查询,值的顺序不同,但作为集合它们仍然是相等的。