[問題案] Set xor-minimum

[windows-server-2003]

問題ID: set_xor_minimum
問題名: Set xor-minimum

想定アルゴリズム: Binary Trie

Binary Trie特有のといえばこれな気がしたので

問題概要

整数の(重複を許す)集合Sがあって最初空です。
クエリをQ個処理してください

• 0 x xをSに1つ追加
• 1 x xをSから1つ削除
• 2 x min_{ i ∈ S } i xor x を出力する

入力

Q
...

出力

2 xの形式のクエリごとに1行ずつ

制約

Q <= 500000 ? 200000 ?
0 <= x < 2^30
2 xが来るときSは空でない

multiじゃないsetにしてもいいかもしれない

[yosupo06]

良さそうです！

問題ID: set_xor_minimum

Set Xor-Min とかかなぁ

multiじゃないsetにしてもいいかもしれない

クエリはmultisetよりsetのほうが自然な気がします、

• 0 x: xがSに含まれてなかったら追加、含まれていたら何もしない
• 1 x : ↑の逆

がいいと思います。

Q <= 500000 ? 200000 ?

実測次第、ですかね…

[windows-server-2003]

あとはxの上限なんですけど2^30か2^31か2^32で悩んでます(10^9に近づけるかsignedに合わせるかunsignedに合わせるか)

[yosupo06]

2^30か2^32かなと思います。どちらでも大丈夫(=この問題を準備する人が好きに決めていい)ですが、個人的には2^30を推しておきます

[windows-server-2003]

分かりました
2^30で僕が作業します