問題概要
問題文 → ■
連想配列（Associative Array）の問題．
単純な処理なので使用頻度はかなり高いです．標準ライブラリを使う場合にパフォーマンスが良い実装方法を確認したり，適切なライブラリを整備する利点はかなり大きいと思います．
解法
標準ライブラリ等の利用
要素数を $N$ としたときに，map による検索は $O(\log N)$ 時間．unordered_map による検索は期待時間 $O(1)$ 時間であるという計算量の違いがあります（ただしその名の示す通り，unordered_map は順序を保持しないため，最小値・最大値や二分探索などは高速には行えません）．
したがって本問の処理では map よりも unordered_map の方が計算量が優れています．ただし $N$ が小さい場合には本問のような処理でも map の方が高速に動作することもあります．
unordered_map は reserve を使って適切なメモリ確保をしておくだけで少し高速になります．
- 解答例（std::unordered_map 使用，reserve あり，139ms）
ところでいずれにせよ，std::unordered_map はかなり遅く，policy hash table を使う方が良いのではないかという話があります（codeforces blog）．std::unordered_map はなぜ遅いのかにもコメントがされていますが，私は詳しく分かっていません．policy based data structures については次の 日本語の文献（Joe さん） も確認しておくとよいと思います．
→ （2024/04/05 現在の Library Checker のジャッジでは，std::unordered_map がかなり遅いということはなさそうです）
- 解答例（__gnu_pbds::gp_hash_table 使用，161ms）
ハッシュテーブルを実装する
実装量も少なめで，上述の手法よりも高速です．あまり余計な機能を持たせず実装した例を挙げておきます．
- 解答例（119ms）
上記の実装は，ハッシュテーブルをオープンアドレス法（開番地法）で実装しています．オープンアドレス法はさらにいくつかの分類がありますが，この実装はそのうち線形探索法ということになります（LC 上位の提出でもほとんどが線形探索法であるように見えます）．どのようなアルゴリズムであるかは実装を見ればかなり理解しやすいと思うので省略します．
ライブラリ化の際には，必要に応じて，テーブルが一定以上埋まってた場合の自動再構築，削除機能をつける，等の機能拡充をすることが考えられます．
オープンアドレス法について
英語版 wikipedia が詳しいです．
キー全体の集合を $S$ とし，テーブルサイズを $n$ とします．$|S|/n = a$ を負荷率といいます．
抽象化されたオープンアドレス法は次のようなものです．
- キーに対して，無限列 $(i_0, i_1, i_2, \ldots)$ を定めるようなハッシュ関数を用意する．
- $(i_0, i_1, i_2, \ldots)$ のうちはじめて未使用のインデックスにデータを置く．
$i_k$ に違うキーのデータが置かれていたという状況を衝突といいます．計算量解析が最も容易なのは，無限列が一様ランダムに定まる場合で，このとき新しいキーに対する衝突回数期待値は $(1-a)^{-1}$ であることが簡単に分かります（確率 $1-a$ で当たりが出るサイコロを当たるまで振るときの回数期待値）．特に，事前に $1$ 未満の正実数を固定して，負荷率をその値以下になる状態を保つように実装すれば，衝突回数の期待値は $O(1)$ で，ハッシュテーブルのもろもろの操作の期待時間計算量が $O(1)$ ということになります．
ただし，一様ランダムな無限列をとるハッシュを作るのは非現実的なので，実用上は次のような選択肢が用いられるようです．
- Linear Probing：列として $i_k=h+k$ の形のものをとる．
- Quadratic Probing：列として $i_k=h+c_1k+c_2k^2$ の形のものをとる．
- Double Hashing：列として $i_k=h_1+h_2k$ の形のものをとる．
Linear Probing はこれらの方法の中では，探索時のキャッシュヒット率が高いというメリット，同じ負荷率に対して衝突回数の期待値が高くなりやすいというデメリットがあります．デメリットについては，一度衝突した場所ほどさらに衝突しやすく，大きな塊（クラスタ）が出来てしまいやすいというのが原因です．
ただし計算量オーダーが $O(1)$ であるという種の性質は大丈夫で，$h$ がキーごとに独立に一様ランダムに定められていて，負荷率が $a$ の場合，衝突回数の期待値が $\Theta((1-a)^{-2})$ であると解析できます（https://en.wikipedia.org/wiki/Linear_probing）．
また，長さ $2^{n+1}$ の配列に $2^n$ 個のキーをセットするという実験を手元で行った結果，$n$ がある程度大きな値のときの衝突回数の平均値は $0.5$ に非常に近い値になりました．
ハッシュ関数について
キーの集合を $S$ として，目標は写像 $S\longrightarrow \{0,1,\ldots,n-1\}$ を一様ランダムに選択することで，計算量解析の類もその前提で行われることがほとんどだと思います．が，実際そんなに都合良く写像を得る方法はありません．
Rolling Hash の場合には，任意の入力に対して十分高い確率で意図通りの動作をするという証明が可能ですが（■），HashMap の場合に「任意の入力（例えば 64bit 符号なし整数からなる任意の長さ $m$ の列）に対して十分高い確率で良い計算量が保証できる」ということが理論的に証明されたハッシュ関数が使われているかどうかは，私は知りません．
標準ライブラリ類を使う場合も，デフォルトで実装されている hash 関数がまあまあダメな場合が珍しくないようで，Python の set, dict や C++ の gp_hash_table も簡単に hack できるということが知られています（■, ■）．
そこで，十分複雑だし hack の仕方が見つけられないなーと思われている写像で計算が高速なものがよく使われているということだと思います．詳しい議論は次のような記事やコメントを参照してください．
なお，ハッシュテーブルの実装において連鎖法（chaining）を使うと，理論保証のあるハッシュが存在するとの情報をいただきました：https://x.com/noshi91/status/1751542895205867703
