Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 228 D 問題 Linear Probing

AtCoder ABC ABC228 D問題 400 pts

問題

提出解答

https://atcoder.jp/contests/abc228/submissions/27409638

問題の概要

$N:=2^{20}$ とする. 長さ $N$ の列 $A=(A_i)_{i=0}^{N-1}$ があり, 最初は全ての項が $-1$ である.

以下の $Q$ 個のクエリを順に処理せよ.

のとき
以下の処理を順に行う.
1. $h \gets x_i \bmod N$ とする.
2. $A_{h \bmod N} \neq 1$ である限り, $h$ に $1$ を加算する.
3. $A_{h \bmod N} \gets x$
$t_i=2$ のとき
$A_{x_i \bmod N}$ を出力する.

制約

$1 \leq Q \leq 2 \times 10^5$
$t_i=1$ または $t_i=2$
$0 \leq x_i \leq 10^{18}$
$t_i=2$ なる $i$ が存在する.
入力は全て整数である.

解法

$2^{20}=1048576 \leq 1.1 \times 10^6$ であるから, 長さ $N$ の列 $A=(A_i)_{i=0}^{N-1}$ を具体的に用意できる. このとき, $t_i=2$ のクエリは単純に $A_{x_i \bmod N}$ を参照し, 出力するだけで完了する.

よって, $t_i=1$ の場合の処理を考える. 愚直な処理では, 2. において, $Q$ クエリの合計計算量が $O(QN)$ となり, 間に合わない. 1.,3. は単純な代入であるから, 2. の処理の高速化を目指すことになる.

$t_i=1$ の処理を観察してみると, 一度更新された要素は二度と更新されないことがわかる. このことを利用して, 以下のように処理を行うことで, 高速に更新すべきインデックスを求めることができる.

最初, $S=\{1,2, \dots, N\}$ とする. この $S$ は $A_k=-1$ となる $k$ 全体の集合とする.
のクエリが来たとき, 以下のように処理する.
- $h \gets x_i \bmod N$ とする.
- $S$ の要素で, $h$ 以上である要素が存在するとき, $h'$ を $S$ にある $h$ 以上の最小の要素とする.
- $S$ の要素で, $h$ 以上である要素が存在しないとき, $h' \gets \min S$ とする.
- $A_{h'} \gets x_i$ とする.
- $S$ から $h'$ を除く.

この処理を高速に行うためのデータ構造の条件は,

$S$ にある $h$ 以上の最小の要素を高速に求めることができる.
$S$ から要素を削除する処理ができる.

である.

これを可能にするデータ構造は, 例えば, 順序付き集合や, Binary Tire などがある. Binary Tire を用いた場合の計算量は, $O(N+Q \log N)$ である.

また, 別解として, Union-Find を用いる方法がある (計算量 $O(N+Q \alpha (N))$