读题容易发现所求即为 $\frac{1}{n}\sum_{i=1}^n\max(i,\frac{\sum_{j=1}^n(i \oplus j)}{n})$，把 $\frac{1}{n}$ 提出来，即 $\sum_i \max(ni,\sum_j (i \oplus j))$。

经过一些打表或者观察可以发现这个 $\max$ 的取值只分成较少个取相同选项的连续段，如果我们能判段 $i$ 属于一个区间的 $\sum_j (i-i \oplus j)$ 符号是否相同就可以实现二分，那么就可以计算答案。

注意对于 $\sum_j (i-i \oplus j)$ 可以拆位，位之间独立，对于一个区间，直接划成 $O(\log n)$ 个高位固定低位任意的区间，每个区间看一下全取最优和全取最劣是否符号相同即可。

但这样子算上二分和计算的复杂度太高了，如果把段数也视为 $O(\log{n})$ 复杂度可能来到 $O(T\log^4{n})$，预处理低若干位任意填的最小贡献和最大贡献可以做到 $O(T\log^3{n})$，不够优秀。

考虑直接对整体分治，这样每次 check 的区间一定是一个trie 树整区间（高位固定低位任意的区间），那么计算贡献和判断符号相当简单。然后只要符号相同就直接计算，不同就暴力递归。精细实现复杂度可以做到 $O(T\log^2{n})$，并且代码更加简洁。