2025.10.23 闲话-全局位运算 \(max\) 的解法
三部分将使用不同的策略求解。
Part.1 \(xor-max\)
这一类问题算是最简单的，每次插入一个数，在 \(Trie\) 树上跳，先查询这个数产生的最大值。
查询时如果当前位是 \(o\) 则优先向 \(!o\) 跳，再向 \(o\) 跳，容易证明一定是最优的（\(o\oplus(!o)=1\), \(o\oplus o=0\)）。
查询完后直接插入 \(Trie\) 树即可。
复杂度 \(O(n\log V)\)。
Part.2 \(and-max\)
这类问题就比较困难了。
因为如果当前位是 1，那么可以大胆的跳 1，然后跳 0。
可是如果当前位是 0，就比较棘手了，因为可以跳 1，也可以跳 0，没有先后顺序，复杂度很容易变得很劣。
这时发现一件事，当前位是 0 时，如果 1 有两个或以上的点经过，那么这两个点一定会与出更优的答案，那么当前这个点就不用去遍历 1 的子树了！
那么只可能有一个点经过 1 时才搜，这时复杂度是 \(O(\log V)\) 的。
总复杂度就是 \(O(n\log^2 V)\)，实测效率趋近较大常数 \(O(n\log V)\)。
另一种做法是暴力合并......这也是对的......（好像被创飞了😭😭😭😭😭😭😭😭😭😭😭😭😭😭）
又精心思考了一下，发现其实暴力合并和这个做法的本质是相同的。
Part.3 \(or-max\)
我不会，求教。