题目链接:https://www.luogu.com.cn/problem/CF1553H
给出\(n\)个在\([0,2^n)\)范围内的数字序列\(a\)。
对于每个\(x\in[0,2^n)\)求
\[\min_{i\neq j}\ |a_i\ xor\ x-a_j\ xor\ x|
\]
\(2\leq n\leq 2^k,1\leq k\leq 19\)
一个很妙的想法，考虑一个数字\(a\)与\(x\)有最多只有前\(d\)位不同的情况，记答案为\(f_{x,d}\)。
考虑这个答案的性质，对于\(x\)找一个一个与它恰好第\(d\)位不同的\(y\)考虑转移，首先显然是从\(min\{f_{x,d-1},f_{y,d-1}\}\)处进行一个转移（因为只多了第\(d\)位可以不同，而此时这两种转移就包括了两个点集内的情况）。
但是还有一种转移有可能是在\(x\)的集合和\(y\)的集合中各自选一个数字，我们可以各自找到两个分别在\(x/y\)的集合中的数字\(a_i\ xor\ x\)最大并且\(a_j\ xor\ y\)最小转移到\(x\)即可。
考虑如何快速找这两个数字，设\(mx_{x,d},mi_{x,d}\)表示上述所示情况下\(x\ xor\ a\)的最大值/最小值，这两个的转移十分显然。
\[mx_{x,d}=max\{mx_{x,d-1},mx_{y,d-1}+2^d\}
\[mi_{x,d}=min\{mi_{x,d-1},mi_{y,d-1}+2^d\}
时间复杂度：\(O(2^kk)\)