题解

20pts

$O(n^2)$ 枚举所有解。

+30pts

注意到可能的 $(a_i,b_i)$ 至多 $O(V^2)$ 种情况，枚举 $i,j$ 对应的 $(a_i,b_i)$ 和$(a_j,b_j)$，时间复杂度为 $O(V^4)$。

+30pts

可能的 $(a_i,b_i)$ 至多 $O(\log^2 V)$ 对，类比之前的做法，时间复杂度为 $O(\log^4 V)$

100pts

首先我们把这题的 $\min$ 给去掉，那么我们按位算贡献，可以求出和。这是这种式子的通用套路。

考虑加上 $\min$，那么我们先按照 $(a_i,b_i)$ 的最高位分为：$(1,0)$，$(0,1)$，$(1,1)$，$(0,0)$​ 四种情况。

先考虑不同的情况，可以发现用贡献的不同的组如下：

• $(0,0),(0,1)$ 贡献为 $a_i⊕a_j$。

• $(0,0),(1,0)$ 贡献为 $b_i⊕b_j$。

• $(1,1),(1,0)$ 贡献为 $a_i⊕a_j$。

• $(1,1),(0,1)$ 贡献为 $b_i⊕b_j$。

• 以下几种可能最高位相同，无法通过最高位比较：

  • $(0,0)$ 与 $(1,1)$
  • $(0,1)$ 与 $(1,0)$

对于无法比较的两组，我们把两组合并起来，然后就变成了子问题，递归处理下一位。

再考虑相同的情况，发现同组内部贡献最高位一定为 $0$，因此可以划分成 $4$ 个子问题继续递归下去。

每次考虑最高层，一共至多递归 $O(\log V)$ 层，时间复杂度为 $O(n \log ^2V)$。