http://codeforces.com/contest/842/problem/D
■「うーん、難しい……」
●「どうしたんですか、先輩」
■「この間のCodeforcesの問題が難しくてね」
●「どんな問題ですか？ ふむふむ、なるほど…… 数列全体に指定の値をXORして、全体のmexを計算するクエリ、ですか。数列の内容は毎回のクエリで変化すると」
mex …… ここでは、集合（数列）に含まれない非負整数のうち、最小のもの
■「そうそう。数列の長さがnで、クエリがm個あるから、O(nm)では解けるんだろうけど」
●「実行時間制限が2msで、n, m≦3*10^5なので、それだとTLEですね」
■「そうなんだよ。毎回のクエリごとに数列の内容が変わるのを保持しようとするとどうしてもO(nm)は掛かっちゃうんだよね……」
●「え？ それは必要無いですよ？」
●「XORには結合法則が成り立つので、(A xor X) xor Y = A xor (X xor Y) です」
■「うん、それはそうだね。 ……あっ、そうか。毎回のクエリは、元の数列全体に (X_1 xor X_2 xor … X_i) をXORすればいいんだ！」
●「その通りです。先輩、しっかりしてくださいよ！」
■「はは、ごめんごめん……」
●「でも、結局O(nm)掛かりそうなのは変わらないですね……」
■「いや、問題がシンプルになるのは良いことだよ。これで独立なクエリに分割できた」
●「これ、制約がちょっと奇妙ですね」
■「制約？」
●「はい。数列の内容が、a_i≦3*10^5 です。どうして上限が10^9じゃないんでしょう？」
■「確かに。何か意味があるのかも。O(max(a_i))みたいな計算量にはならなさそうだから、メモリが足りることが重要……？」
●「なるほど、確かに、今回は要素数 max(a_i) の配列も使えますね」
■「とりあえず、3つ目の入出力例で試してみよう。元の数列は{0, 1, 5, 6, 7}、2進数で書くと{000, 001, 101, 110, 111}だね」
●「元の数列のmexは2ですね」
■「全体に1をXORすると……」
000 → 001
001 → 000
101 → 100
110 → 111
111 → 110
■「{1, 0, 4, 7, 6}になって、mexは変わらず2だね」
●「最下bit以外が同じ数の組（0と1, 6と7）で、大小関係が逆転してますね」
■「それはそうだね。0が1になって、1が0になるんだから」
●「1が2つ以上立ってる数をXORするとどうなるんでしょう？」
■「5（2進数で101）をXORしてみようか」
000 → 101 (5)
001 → 100 (4)
101 → 000 (0)
110 → 011 (3)
111 → 010 (2)
■「mexは1になったね」
●「下から3bit目を境に大小が入れ替わってますね。さらにその中で、2bit目では通常通りの大小関係になっていて、1bit目の大小関係が入れ替わってます」
■「当たり前といえば当たり前だけど、確かにそうなってるね」
●「つまり、101をXORした場合に小さい値を探す場合は、下から3bit目が1のもの、2bit目が0のもの、1bit目が1のものを探せば良いんですね」
■「でも、今探してるのは最小値じゃなくてmexだよ？」
●「そうですね…… 小さい値を探して、数列に存在したら次に小さい値を探す、それも存在したらさらに次の値を探す、みたいな……」
■「それだと1回の探索にO(n)掛かっちゃうよね。数列が{0, 1, 2, …}で、0をXORするクエリが並んでたりするとTLEだよ」
●「それはそうなんですけど……」
●「XORする数が分かっていれば、大小関係は上の桁から見れば良くて、小さい順に見て存在しないものが見つかればそれが答えで、えーと、明らかに無駄な探索を省略すると、下が全部埋まっているものを見る必要が無くて、その情報はメモリが足りるから最初に計算できて、んー、trieみたいな？ 完全二分木か……」
■「あの、どうしたの？ 何が起こってるの？ trieって文字列検索で使うものだったと思うけど……」
●「ああ、すみません先輩。独り言です。でも、ちょっと光が見えてきました」
●「先輩、元の数列のmexが4になる条件は何ですか？」
■「元の、ってことは何もXORせずにってこと？ なら、元の数列に0, 1, 2, 3が含まれていることが条件だけど」
●「この場合、例えば3をXORしてもmexが4以上なのは変わらないですよね？」
■「えーと、3をXORすると下位2bitが反転するけど、00, 01, 10, 11の全部が存在するから、反転させても0, 1, 2, 3は存在することになるね」
●「ですよね。つまり、この場合、”0??”みたいな数は見る必要が無いんですよ」
■「んーと、どういうこと？」
●「例えば元の数列が{0, 1, 2, 3, 5, 6, 7}だとします」
■「うん」
●「2進数にすると、こんな感じです」
000
001
010
011
101
110
111
■「うん」
●「ここで、001、つまり1をXORしたときのmexを探します」
■「最下bitのみの反転だから、{0, 1, 3, 2, 4, 7, 6}になって、mexは5か」
000 → 001 (0)
001 → 000 (1)
010 → 011 (3)
011 → 010 (2)
101 → 100 (4)
110 → 111 (7)
111 → 110 (6)
●「元の数列の2進数表示から、”001をXORしたときのmex”を探すとき、まず3bit目が0のものを探したくなります」
■「XORする数は001で、3bit目が0だから、大小関係はそのまま（0の方が小さい）だからだよね。小さい数を探すわけだから」
●「ですが、その必要はありませんよね？」
■「えーと、ああ、そうか。3bit目が0のものは全種類（4種類）そろっているから、下2bitがどうなっていようと、全部存在するんだね」
●「その通りです。なので、いきなり3bit目が1のものをチェックします」
■「次もXORする数字の2bit目が0だから、2bit目が0のものからチェックしたいね」
●「はい。現在”10?”を調べています。最下bitは、1の方が小さいので、”101″の有無を調べます」
■「XORする数の最下bitが1だから、100より101の方が小さくなるんだね」
●「101が元の数列に存在するので、次に100をチェックします」
■「100は元の数列には無いね。これがmexか」
●「001をXORするのを忘れないでくださいね！」
■「ああ、そうだった。100 xor 001 = 101 (5)が答えだね。うん、合ってる」
●「さて、この探索では、以下のような動きをしましたね」
１－１．XORする数001の3bit目が0なので、元の数列から3bitのものを探す
１－２．3bit目が0のものが全部埋まっているので、3bit目が1のものを探す
２－１．XORする数の2bit目が0なので、元の数列から（3bit目が1のものの中で）2bit目が0のものを探す
３－１．XORする数の1bit目が1なので、元の数列から（3,2bit目が”10″のものの中で）1bit目が1のものを探す
３－２．（3,2bit目が”10″のものの中で）1bit目が1のものが全て埋まっているので、1bit目が0のものを探す
４－１．”101″が元の数列に存在しないので、これに001をXORしたものが答えとなる
■「ややこしいけど、そうだね。各桁について、”その桁以下が埋まっているか”を調べているね。埋まってたら、見る必要が無い。でも、”その桁以下が埋まっているか”って調べるの大変じゃない？」
●「それは事前に計算できますよ」
●「2進数を、完全二分木で表現します」
■「上の子が0、下の子が1ってことだね。赤いのは？」
●「右端では、数列に存在する数のみ赤で塗ってあります」
■「{0, 1, 2, 3, 5, 6, 7}だね。途中のは？」
●「2つの子が両方とも赤いものだけ赤で塗ってあります」
■「なるほど、こうすると”全ての子孫が元の数列に存在するノード”のみが赤くなるんだね」
●「はい！ 001をXORする場合のmexを探索するイメージは、無駄な探索を含めると、こんな感じです」
■「なんか、線がぐにゃぐにゃだね」
●「ほっといてください！ ペンタブ持ってないんです！」
■「それはさておき、上半分で無駄なことをしているように見えるね」
●「はい。存在する数ばかりのエリアを探索しています。これは、赤いノードより深く入らないことで回避できます」
■「だいぶすっきりしたね」
●「赤いノードにぶつかったら、それ以降はどこへ行っても元の数列に存在する値にしか行きつかないので、引き返しています」
■「なるほど、これだと、1回のmex探索がO(桁数)=O(log(max(a_i)))で可能だね。logは定数だから実質O(m)で解けるね」
●「logは定数って、いつか痛い目に遭いますよ……」
■「理屈は分かったけど、実装がやや面倒かなあ」
●「そうですか？」
■「木を作らないといけないから……」
●「いえ、今回は完全二分木なので、セグメント木っぽく配列で作れますよ」
■「ああ、なるほど、1-indexedで、子は2*iと2*i+1ってやつか」
●「え？ セグ木は0-indexedでしょう？」
■「あ、この話はやめとこう」
●「親は(i-1)/2ですからね！ 今回は使いませんけど！」
■「えーと、とりあえずセグ木っぽいの（完全二分木）を実装して、ノードにbool値を持たせればいいのか。デフォルトはfalseで、与えられた数列の要素について”その値に対応する二分木の葉ノードの値をtrueにする”とすればいいのか」
●「そして、DFSで帰りがけ順に”子が両方ともtrueなら自身もtrueにする”とすればOKです」
■「mex探索は、二分木の根から、最上bit（下から19bit目）から見ていけばいいんだね」
●「そうですね。XORする数の対応するbitが0か1かで、子の探索順を変更して、行きたい子がtrueならもう片方の子に入る、と」
■「このとき、両方の子がtrueということはあり得ないね。それだと今いる場所もtrueのはずだから」
●「はい。なのでO(桁数)になるんですね」
■「よし、実装できた。Codeforcesからsubmitして…… お、通った！」
●「おめでとうございます、先輩！」
■「これは君のおかげだよ」
●「いや、そんなことは…… ありますかね……？ 確かにそうですね！ 私のおかげです！」
■「遠慮はしないのね……」
（作者注：執筆時にCodeforcesのジャッジが止まっており、上記コードは実際はsubmitしておりません。サンプルは通っているのですが、間違っているかもしれません。ジャッジが動き次第、確認しますACしていました）