题目描述

blablabla

翻译Y神拉链法

N = 100003

e = [0]*N 
ne = [0]*N
h = [-1]*N
idx = 0

def insert(x):
    global e, ne, h, idx
    k = (x % N + N) % N
    e[idx] = x
    ne[idx] = h[k]
    h[k] = idx
    idx += 1

def find(x):
    global e, ne, h, idx
    k = (x%N + N)%N
    i= h[k]
    while i != -1:
        if e[i] == x:return True
        i = ne[i]
    return False

if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        line = list(input().split())
        opt = line[0]
        x = int(line[1])
        if opt == 'I':
            insert(x)
        elif opt == 'Q':
            if find(x):
                print("Yes")
            else:
                print("No")

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla