01Trie题解

The XOR Largest Pair
考虑将前i个数插入到01Trie中，那么我们考虑第(i+1)个数时只需要在01Trie中查询最大值即可。

奶牛异或
和第一题一样，不过只需要在01Trie的叶子节点多维护一个pos信息即可，查询返回二元组(ans, pos)

Vitya and Strange Lesson
先把给出的集合unique一下，在01Trie节点上维护一个sz表示子树大小，那么我们查询的时候可以按从高位往低位贪心，如果与第i位相同的节点sz值等于，那么就往不同的方向走，并将答案+。

Perfect Security
与上一题一样多维护sz信息，由于每个值只能用一次，因此在查询的时候边查询边删除节点(通过减sz的方法)。

Xor-MST
由boruvka最小生成树算法可以得出以下的按位分治算法:
同样从高位往低位考虑，假设当前考虑到了第位，我们把当前集合分裂成第位为0的集合和为1的集合，然后用01Trie求出从两个集合中各取一个数使得异或值最小.
然后继续对两个集合继续分治.
分析一下复杂度，分治深度为，每一层需要用01Trie处理个数，因此复杂度为

最大异或和
使用可持久化的01Trie，01Trie可持久化的思路与线段树可持久化的思路一致(或者说两者就是同一个东西)，由于每次插入最多只会修改log个节点，因此对于每次修改我们都新建一个根，对于不变的节点我们直接继承上一个，修改的节点重新申请内存.这样我们就可以查询第i个版本的01trie.
对于这道题，对于查询我们将异或一下整个数组的值，这样我们就将问题转化为查询中的一个p使得最大。