异或

这是一道非常巧妙的位运算和分治（Trie树思想）的算法竞赛题。从数据规模来看，要求我们在 或 的时间复杂度内解决问题。

下面为你详细剖析这道题的核心思路，并提供完整的 C++ 满分解法。

核心思路与数学转化

题目要求计算所有无序对 的能力值之和，能力值定义为：

直接计算由于需要比较大小， 函数和异或操作非常难直接融合。我们需要寻找 和 之间的大小规律。

不妨设 。
那么我们观察两者异或的结果：

这意味着，两个能力候选值不同的最高位，就是 的最高位为 1 的位置！

假设 的最高位 1 在第 位：

1. 因为是最高位，对于所有比 高的位 ()， 的第 位都是 0。这说明 。即：第 位以上的高位，二者完全相同，不影响大小比较。
2. 决定 取值的就是第 位。因为 ，说明 和 在第 位不同，必然是一个为 0，另一个为 1。

3. 不妨设 ：

   • 和 第 位相同，设均为 。
   • 和 第 位不同。必然有一个是 ，另一个是 。
   • 谁能让异或结果的第 位变成 0，谁就是更小的！
   • 所以，如果我们需要选出的值在第 位为 0，只需选择 的属性中（ 或 ），第 位为 的那一项即可。

算法设计 (Trie / 分治)

我们可以基于 的二进制位从高到低（第 17 位到第 0 位）进行分治求解：
对于当前的候选集合 indices 和当前处理的位数 bit：

1. 根据每个元素 的第 bit 位是 0 还是 1，将当前集合划分为两个子集： 和 。
2. 递归处理内部对：solve(S0, bit - 1) 和 solve(S1, bit - 1)。

3. 计算 和 之间两两配对的贡献（这是当前层的核心）：
   因为 ，它们 的最高位恰好就是当前的 bit！
   根据我们前面的数学推导：

   • 如果 且它的第 bit 位（ 和 均相同）为 0，那么为了取得 ，我们需要拿 中第 bit 位同样是 0 的那个属性来和 异或。
   • 同理，如果 且它的第 bit 位为 1，我们需要拿 中第 bit 位同样是 1 的属性来和 异或。

通过这种“拆分”，我们可以把 和 拆成几个数组，分别把 和 对应的正确的项存入数组。最后在这几个数组之间利用按位拆分计算组合异或和（时间复杂度 ），即可在极快的速度下算出所有交叉对的 和。

4. 边界条件：如果 bit < 0，说明进入同一叶子的所有元素 均相同，此时 恒等于 ，直接计算它们之间两两 的和即可。

C++ 参考代码

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> a, b, c;

// 计算两个集合 A 和 B 之间所有对的异或和： sum(x ^ y) for x in A, y in B
long long sum_xor(const vector<int>& A, const vector<int>& B) {
    if (A.empty() || B.empty()) return 0;
    long long total = 0;
    // 数据小于 2^18，所以遍历 0 到 17 位
    for (int bit = 0; bit < 18; ++bit) {
        long long cnt1_A = 0, cnt1_B = 0;
        for (int x : A) {
            if ((x >> bit) & 1) cnt1_A++;
        }
        for (int x : B) {
            if ((x >> bit) & 1) cnt1_B++;
        }
        long long cnt0_A = (long long)A.size() - cnt1_A;
        long long cnt0_B = (long long)B.size() - cnt1_B;
        // 当前位为 1 的组合数
        long long pairs = cnt1_A * cnt0_B + cnt0_A * cnt1_B;
        total += pairs * (1LL << bit);
    }
    return total;
}

// 分治主函数
long long solve(const vector<int>& indices, int bit) {
    if (indices.empty()) return 0;
    
    // 递归边界：所有剩余元素的 c_i 全部相同，此时 a_x ^ a_y == b_x ^ b_y
    if (bit < 0) {
        long long total = 0;
        for (int b_idx = 0; b_idx < 18; ++b_idx) {
            long long cnt1 = 0;
            for (int idx : indices) {
                if ((a[idx] >> b_idx) & 1) cnt1++;
            }
            long long cnt0 = (long long)indices.size() - cnt1;
            total += cnt1 * cnt0 * (1LL << b_idx);
        }
        return total;
    }

    vector<int> S0, S1;
    S0.reserve(indices.size());
    S1.reserve(indices.size());

    // 根据 c_i 的第 bit 位划分为两个集合
    for (int idx : indices) {
        if ((c[idx] >> bit) & 1) {
            S1.push_back(idx);
        } else {
            S0.push_back(idx);
        }
    }

    vector<int> L0a, L0b, L1a, L1b;
    for (int x : S1) {
        if (((a[x] >> bit) & 1) == 0) {
            L0a.push_back(a[x]); // a_x 第 bit 位是 0
            L1b.push_back(b[x]); // b_x 第 bit 位是 1
        } else {
            L0b.push_back(b[x]); // b_x 第 bit 位是 0
            L1a.push_back(a[x]); // a_x 第 bit 位是 1
        }
    }

    vector<int> R0a, R0b, R1a, R1b;
    for (int y : S0) {
        if (((a[y] >> bit) & 1) == 0) {
            R0a.push_back(a[y]);
            R0b.push_back(b[y]);
        } else {
            R1a.push_back(a[y]);
            R1b.push_back(b[y]);
        }
    }

    long long ans = 0;
    // 组装合并跨集合产生的答案
    ans += sum_xor(L0a, R0a);
    ans += sum_xor(L0b, R0b);
    ans += sum_xor(L1a, R1a);
    ans += sum_xor(L1b, R1b);

    // 递归处理子树内产生的答案
    ans += solve(S0, bit - 1);
    ans += solve(S1, bit - 1);

    return ans;
}

int main() {
    // 关闭同步流，加速 cin/cout，防止大量输入数据超时
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> n)) return 0;
    
    a.resize(n);
    b.resize(n);
    c.resize(n);
    
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        c[i] = a[i] ^ b[i]; // 预处理异或数组
    }

    vector<int> initial_indices(n);
    for (int i = 0; i < n; ++i) initial_indices[i] = i;

    // 从最高位（因为数据限制 < 2^18，所以最高为17位）开始分治
    cout << solve(initial_indices, 17) << "\n";
    
    return 0;
}

复杂度分析

• 时间复杂度：共有 层递归，每一层中的总元素数量为 。而在处理 sum_xor 合并答案时，又需要循环 次拆分二进制位。所以总体的时间复杂度为 。
  代入极值，运算大概需要 $2 \times 10^5 \times 18 \times 18 \approx 6.48 \times 10^7$ 次计算，在常规 1 秒 限制下跑得绰绰有余（一般 C++ 1s 能承受接近 $10^8 \sim 5 \times 10^8$ 次操作）。
• 空间复杂度：由于只存在常数倍开销（动态局部数组），最大递归深度也是 且同一深度局部变量总内存占用受限于总体 ，因此空间复杂度稳定在 。