題目連結: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)\)