tomerun https://blog.hatena.ne.jp/tomerun/ TopCoderの学習のお時間 https://topcoder-tomerun.hatenablog.jp/ しばしばマラソン（ヒューリスティック）コンテストで使うやつです。 値の追加・削除・存在確認が、最悪時間計算量が定数倍の軽い O(1)、 空間計算量が O(n) でできます。 入っている値を他の値で置き換えるとか、入っている値からランダムに1つ返すとかも簡単にできます。 仕組みとしては単純で、集合に入っている値を保持する que と、 [0,n) の各整数が que の何番目に入っているかを保持する pos の2つを操作します（queと言いつつキューではない）。 エラー処理は入れてないので必要に応じて。 struct IndexSet { vector<int> que; vector<int>… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftopcoder-tomerun.hatenablog.jp%2Fentry%2F2021%2F06%2F12%2F134643" title="[0,n)の整数の集合を管理する定数倍が軽いデータ構造 - TopCoderの学習のお時間" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-06-12 13:46:43 rich https://topcoder-tomerun.hatenablog.jp/entry/2021/06/12/134643 1.0 100%