ARC127 Sum of Min of Xor()

可以发现 \(a_i \bigoplus b_i \bigoplus a_j \bigoplus b_j\) 为 \(1\) 的位置,是 \(a_i \bigoplus a_j\) 与 \(b_i \bigoplus b_j\) 不同的位置。
设 \(c_i = a_i \bigoplus b_i\),考虑根据上个性质分治,每次吧在当前位数 \(dep\) 为 \(0\) 的 \(c_i\) 放入一个集合中,\(1\) 的放在另一集合,那么这两个集合之间 \(a_i \bigoplus a_j\) 和 \(b_i \bigoplus b_j\) 不同的最高位就是 \(dep\),判断他们的大小关系只需要考虑在 \(dep\) 位上的大小关系即可。
Tips:
涉及 \(a_i, a_j, b_i, b_j\) 的题目可以考虑讲 \(a_i\) 和 \(b_i\) 合并。

————————

可以发现 \(a_i \bigoplus b_i \bigoplus a_j \bigoplus b_j\) 为 \(1\) 的位置,是 \(a_i \bigoplus a_j\) 与 \(b_i \bigoplus b_j\) 不同的位置。
设 \(c_i = a_i \bigoplus b_i\),考虑根据上个性质分治,每次吧在当前位数 \(dep\) 为 \(0\) 的 \(c_i\) 放入一个集合中,\(1\) 的放在另一集合,那么这两个集合之间 \(a_i \bigoplus a_j\) 和 \(b_i \bigoplus b_j\) 不同的最高位就是 \(dep\),判断他们的大小关系只需要考虑在 \(dep\) 位上的大小关系即可。
Tips:
涉及 \(a_i, a_j, b_i, b_j\) 的题目可以考虑讲 \(a_i\) 和 \(b_i\) 合并。