色々な解き方があるなぁ．．．
解法1：片方の集合を前から見ていく（もう一方は包含される範囲を見る）
考え方
一番自然な考え方だと思うが，見落としがあるとすぐバグる．「$A$の先頭〜今見ている元からなる集合」と「$B$の先頭〜今見ている元からなる集合」の差を$A\setminus B$，共通部分を$A\cap B$と略記する．
ok[i]=【「$A$の$i$番目までの集合」= 「$B$の$j$番目までの集合」を満たす$j$の集合】として，$A$が空になるまで以下を続ける．「$B$の先頭〜見ている範囲」が「$A$の先頭〜見ている範囲」に常に包含されていることに注意．
- $A$の先頭を取り出す（これは常に$A\setminus B$の元になる）
- $B$の先頭が$A\setminus B$か$A\cap B$に含まれるなら取り出す．このとき，
- $A\setminus B$に含まれる場合は，$A\setminus B$と$A\cap B$を更新する
- $A\setminus B$が空なら，見ている範囲で$A$と$B$が一致しているので，
ok[i]を記録する．
- $A$の先頭が$A\cap B$に含まれているなら，1コ前の答えと同じになる．
回答例
AmB$=A\setminus B$AaB$=A\cap B$
from collections import deque N = int(input()) A = list(map(int, input().split())) A = deque((i, A[i]) for i in range(N)) B = list(map(int, input().split())) B = deque((i, B[i]) for i in range(N)) ok = [set() for _ in range(N)] AaB = set() AmB = set() while A: i, a = A.popleft() AmB.add(a) while B and ((B[0][1] in AmB) or (B[0][1] in AaB)): j, b = B.popleft() if b in AmB: AmB.remove(b) AaB.add(b) if not AmB: ok[i].add(j) while A and (A[0][1] in AaB): i, a = A.popleft() ok[i] = ok[i - 1] Q = int(input()) for _ in range(Q): x, y = map(lambda x: int(x) - 1, input().split()) if y in ok[x]: print('Yes') else: print('No')
解法2：種類数が同じ場合だけ考える
考え方
Editorial - AtCoder Beginner Contest 250「$(a_{1}, ..., a_{x_{i}})$までに現れる種類数」と「$(b_{1}, ..., b_{y_{i}})$までに現れる種類数」が等しくなければNoが確定する．
よって，種類数が同じ場合の答えがわかれば良い．具体的には，「$A$の$i$種類目までの集合」が，「$B$の$i$種類目までの集合」と等しければYesで，そうでなければNoとすればよい．
$i$番目までの集合が等しいことは，例えば以下でわかる．
- $A,B$のそれぞれについて$i$種類目の数を求めておく．
- 空の集合$S$を用意する．
- $i = 1,2,...$について，順に次の操作を行う：
- $A$の$i$種類目が集合$S$に入っていれば$S$から取り除き，入っていれば$S$に追加する．
- $B$の$i$種類目が集合$S$に入っていれば$S$から取り除き，入っていれば$S$に追加する．
- $S$が空なら「$A$の$i$種類目までの集合」=「$B$の$i$種類目までの集合」であり，空でないなら≠となる．
回答例
N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) numa = [0] * (N + 1) dicta = {} numb = [0] * (N + 1) dictb = {} tmp = set() for i, a in enumerate(A): numa[i + 1] = numa[i] if a not in tmp: numa[i + 1] += 1 tmp.add(a) dicta[len(tmp)] = a tmp = set() for i, b in enumerate(B): numb[i + 1] = numb[i] if b not in tmp: numb[i + 1] += 1 tmp.add(b) dictb[len(tmp)] = b ans = ['No'] * (N + 1) tmp = set() for i in range(1, N + 1): if i in dicta: if dicta[i] in tmp: tmp.remove(dicta[i]) else: tmp.add(dicta[i]) if i in dictb: if dictb[i] in tmp: tmp.remove(dictb[i]) else: tmp.add(dictb[i]) if not tmp: ans[i] = 'Yes' Q = int(input()) for _ in range(Q): x, y = map(int, input().split()) if numa[x] != numb[y]: print('No') else: print(ans[numa[x]])
解法3：種類数が同じ場合だけ考える & 数値の置き換え
考え方
Editorial - AtCoder Beginner Contest 250数字を$A,B$の登場順に$0$から置き換える．
そうすると，「$A$の$i$種類目までの集合」と「$B$の$i$種類目までの集合」が等しいかどうかは，「$A$の$i$種類目までの集合の最大値」と「$B$の$i$種類目までの集合の最大値」が等しいかどうかで判定できる．
回答例
N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) d = {} i = 0 for x in A + B: if x in d: continue d[x] = i i += 1 A = [d[a] for a in A] B = [d[b] for b in B] numa = [0] * (N + 1) tmp = set() for i, a in enumerate(A): numa[i + 1] = numa[i] if a not in tmp: numa[i + 1] += 1 tmp.add(a) numb = [0] * (N + 1) tmp = set() for i, b in enumerate(B): numb[i + 1] = numb[i] if b not in tmp: numb[i + 1] += 1 tmp.add(b) maxa = [-1] * (N + 1) for i in range(N): maxa[i + 1] = max(maxa[i], A[i]) maxb = [-1] * (N + 1) for i in range(N): maxb[i + 1] = max(maxb[i], B[i]) Q = int(input()) for _ in range(Q): x, y = map(int, input().split()) if numa[x] == numb[y] and maxa[x] == maxb[y]: print('Yes') else: print('No')
