/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ 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と出力せよ。
制約
- 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 が 1 個ずつ、B の先頭 3 項には 1 が 1 個と 2 が 2 個含まれます。しかし、それぞれに含まれる値の集合はどちらも \{ 1,2 \} となり、一致します。
また、6 番目のクエリにおいては各値が現れる順番が異なりますが、やはり集合としては一致します。
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.