ABC250 E - Prefix Equality

atcoder.jp

先頭xおよびy要素のそれぞれの集合を事前に作っておいて、一致確認できれば簡単だけど、それをやるとTLEする。ある集合の状態をもっと軽量な値として管理したらよさそうで、それをハッシュ的にやる。

初登場の要素が来たら、乱数を生成して、ある要素に対するハッシュ値とする（値域が大きいため、事前にテーブル化はできず、defaultdictでやった）。で、AおよびBのある要素までのハッシュ累積和的なもの（集合を示したいので、集合に変動がない限り、値も変えない）を作っておくことで、集合のハッシュ化的なことができる。

from collections import defaultdict
import random


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    Q = int(input())

    D = defaultdict(int)

    ruiSA = [0] * N
    ruiSB = [0] * N
    SA = set()
    SB = set()
    hashA = 0
    hashB = 0
    for i in range(N):
        if D[A[i]] == 0:
            D[A[i]] = random.randint(0, 10 ** 10)
        if D[B[i]] == 0:
            D[B[i]] = random.randint(0, 10 ** 10)

        if A[i] not in SA:
            hashA += D[A[i]]
        ruiSA[i] = hashA

        if B[i] not in SB:
            hashB += D[B[i]]
        ruiSB[i] = hashB

        SA.add(A[i])
        SB.add(B[i])

    for i in range(Q):
        x, y = map(int, input().split())
        if ruiSA[x - 1] == ruiSB[y - 1]:
            print("Yes")
        else:
            print("No")


resolve()