愚直解法

\(t_i = 1\) であるようなクエリにおいて、\(h\) の値を \(1\) ずつ増やす処理を愚直に行うとします。この方法では、例えば次のケースで計算量が \(\Theta (Q^2)\) となります :

• 全てのクエリに対し \(t_i = 1\) かつ \(x_i \bmod N = 0\) である。

解法 1

\(A_i = -1\) であるような \(i\) の集合は \(O(Q)\) 個の区間の和集合として表せます。それらの区間が \([l_1, r_1), [l_2, r_2), \dots, [l_n, r_n)\) であるとし、\(l_1 \lt r_1 \lt l_2 \lt r_2 \lt \dots \lt l_n \lt r_n\) が成り立つとします。

\(0 \leq h \lt N\) に対し、\(h\) を値を \(1\) ずつ増やしていき、初めて \(A_{h \bmod N} = -1\) となったときの \(h \bmod N\) の値を \(p(h)\) と表すことにします。

• \(r_n \leq h\) のとき、\(p(h) = l_1\) です。
• \(h \lt r_n\) のとき、\(h \lt r_k\) となる最小の \(k\) を \(m\) とおくと、次のようになります。
  • \(l_m \leq h\) のとき、\(p(h) = h\) です。
  • \(h \lt l_m\) のとき、\(p(h) = l_m\) です。

\(t_i = 1\) であるようなクエリについては、\(k = p(x_i \bmod N)\) とおいたとき、\(A_k \leftarrow x_i\) とすればよいです。この際、\([l_1, r_1), [l_2, r_2), \dots, [l_n, r_n)\) を更新する必要があります。これは次のように行います :

• \(l_m \leq k \lt r_m\) となる区間を一意にとり、\([l_m, r_m)\) を削除する。
• \(l_m \lt k\) ならば、\([l_m, k)\) を新たに追加する。
• \(k + 1 \lt r_m\) ならば、\([k + 1, r_m)\) を新たに追加する。

区間の追加 / 削除および \(h \lt r_k\) となる最小の \(k\) を求める操作は、平衡二分探索木やフェニック木などのデータ構造を用いて \(O(\log Q)\) で実現することができます。C++ であれば、std::set や std::map を用いることができます。

\(A_i\) の値を読み書きする処理は、全ての要素を配列で管理するならば空間計算量 \(\Theta (N)\) クエリあたりの時間計算量 \(O(1)\) となり、\(A_i \neq -1\) である要素のみを辞書型などで管理するならば空間計算量 \(O(Q)\) クエリあたりの時間計算量 \(O(1)\) または \(O(\log Q)\) となります。

以上をまとめて、この問題を \(O(N + Q\log Q)\) または \(O(Q\log Q)\) の計算量で解くことができました。後者は \(N\) に依存しない計算量となっています。

実装例 (C++)

解法 2

\(0 \leq h \lt N\) に対し、\(h\) を値を \(1\) ずつ増やしていき、初めて \(A_{h \bmod N} = -1\) となったときの \(h \bmod N\) の値を \(p(h)\) と表すことにします。

\(p(h)\) を求めるための補助的な数列 \(P = (P_0, \dots, P_{N - 1})\) を用意し、\(P_h = h\) と初期化しておきます。

\(p(h)\) を求める際は、次のようにします。

• \(A_h \neq -1\) である間、\(h \leftarrow P_h\) とすることを繰り返す。

また、\(A_k = -1\) である要素を \(-1\) でない値で書き換えるとき、\(P_{k} \leftarrow p(k + 1)\) と更新します。

上記の操作が Union-Find と呼ばれるデータ構造に類似していることに気づきましたか？経路圧縮と呼ばれる手法を用いることで、各操作を償却 \(O(\log N)\) で行うことができます。

以上をまとめて、この問題を \(O(N + Q\log N)\) の計算量で解くことができました。

実装例 (C++)

余談

この問題は、ハッシュテーブルの手法の一つである開番地法における線形探索法 に基づいています。
「愚直解法」の節で挙げたように、\(x_i \bmod N\) の分布にばらつきがあると、処理に要するステップ数が多くなってしまいます。高速なハッシュテーブルを実現するためには、値がくまなく分布するハッシュ関数を用いることが重要です。