Readme

2935.Maximum-Strong-Pair-XOR-II

观察|x - y| <= min(x, y)， 假设x是其中较大的那个，很容易推得y<=x<=2y。所以我们将nums从小到大排序之后，考察某个数作为y时，可以将一段滑窗内的元素[y,2y]加入一个集合，根据y在这个集合里找能与y异或得到最大值的那个元素。并且，我们发现随着y的移动，这个滑窗的移动也是单调的，说明每个式子进入集合与移出集合都只需要操作一次，时间复杂度是o(N).

对于求最大XOR pair而言，这样的“集合”必然是用Trie。将符合y条件的数字加入Trie之后，从高到低遍历y的每个bit位：如果y的bit是1，那么我们就选择在Trie里向下走0的分支（如果存在的话），反之我们就在Trie里向下走1的分支。这样走到底之后，你选择的路径所对应的数字就是能与y异或得到最大的结果。

PS：在Trie里实时加入一条路径很简单，但是如何移除一条路径呢？显然不能盲目地删除该路径上的所有节点，因为它可能被其他路径共享。技巧是，给每个节点标记一个计数器。加入一条路径时，将沿路的节点的计数器加一；反之删除一个条路径时，将沿路的节点的计数器减一。如果某个节点的计数器为零，意味着该分支已经“虚拟地”从Trie里移出了，就不能再被访问了。