ABC228D - Linear Probing

【関連】

• UnionFind木 - 競プロはじめました

考え方

$2^{10} = 1024$だから，$N= 2^{20}\simeq 10^{6}$．

操作で時間がかかるのは$t_{i} = 1$の2. の部分．これを高速化するには，与えられた$x_{i}$に対しx[i] += 1$\pmod{N}$を繰り返し，はじめて$A_{k} \neq -1$なる$k$を高速に求めるようにすれば良い．

これは，UnionFind木をつかって，

• $A_{k} \neq -1$である区間を管理し，
• 区間の親を，k += 1$\pmod{N}$で初めて$A_{k} = -1$となる$k$にする

とすればよい．言い換えれば，$A_{k} \neq -1$である区間を$[\text{start}, \text{end})$の形で管理することになる．

あとは，端（$k=N-1$）に来たら$k=0$に戻ることに気をつける．

回答例

Q = int(input())
N = 1 << 20
A = [-1] * N

p = [-1] * N
def root(x):
  if p[x] < 0:
    return x
  p[x] = root(p[x])
  return p[x]
 
def merge(x, y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  p[x] = y
  
for _ in range(Q):
  t, x = map(int, input().split())
  h = x % N
  if t == 1:
    A[root(h)] = x
    merge(root(h), (root(h) + 1) % N)
  else:
    print(A[h])

【参考】Submission #27406992 - TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228)