\(C_{i},D_{i},K\) を二進法で \(X=30\) 桁の数として考えます。

パート1

\(Q=1\) のとき、変数 \(ans=0\)、整数列 \(p=(1,2,...,M)\)、 \(N\) 頂点のグラフ \(G\) を用意して、 \(i=X-1,X-2,...,0\) の順に以下の操作をすることで、答えが求まります。

\(p\) の要素 \(x\) を前から見て、 \(C_{x}\oplus D\) の \(i\) 桁目と \(K\) の \(i\) 桁目が違うなら数列から \(x\) を取り除き、もし \(K\) の \(i\) 桁目が \(0\) ならば \(G\) の頂点 \(A_{x},B_{x}\) を結ぶ辺を追加し、 \(ans\) を更新する。

\(ans\) を更新する部分は Union Find Tree を用いて求めます。

\(ans\) を更新する部分については過去にABCで出題されているので、こちらを参考にしてください。

パート2

これを \(D\) の昇順にします。 例えば、 \(D_{1}=00101,D_{2}=00111\) としたとき(ここだけ \(X=5\) 桁)、上の\(3\) つの桁 \(001\) の部分は上でする操作が同じです。

よって、\(D_{1}\) を求めた後、 \(001\) の部分まで戻った後、残りの \(11\) の部分を求めることで \(D_{2}\) を求めます。この戻るという操作は undo 付き Union Find Tree で 一つの辺ごとに \(O(\log N)\) で行えます。

各辺ごとに、辺を付ける、外すという操作は高々 \(2X\) 回であるため、全体で \(O(X(Q+M\log N))\) で全てのクエリに対する答えを求めることができます。

実際の実装では再帰関数を用いた方が楽かもしれません。

実装例 C++

実装例 pypy3