题解 | #小美的区间异或和#

读题，可以发现题目要求的是所有的数对的xor值的贡献之和。那么这里的贡献是什么呢？ 注意所有连续子数组，其实可以等价于找到两个数字，然后分别向左边和右边扩展后得到的区间，在这些区间里，我们找到的这对数字是可以为答案做出贡献的。 假设我们的数组是1-下标的，我们找到的第一个数字下标为l，第二个数字下标为r，那么这对数字对于答案的贡献就是。 那么为了计算这个答案，可能会想到用

for (int i = 1; i < n + 1; i ++) {
  for (int j = i + 1; j < n + 1; j ++) {
    ans += i * (n - j + 1) * a[i] ^ a[j];
  }
}

来计算，但这样显然不能通过n = 1e5 的测试。可以发现，其实每个j都是可以预先计算出来的，也很容易做到增加和删除，可以在读入的时候直接把j加入数组记录，删除的时候也可以直接删除某一个j的值，这些都很方便。这样可以优化上述公式里计算j的部分。 那对于公式里异或的计算，可以按位考虑，把j直接记录进每一位上，这样可以通过遍历每一位来快速计算异或值。

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> v(n), nums(33);
    for (int i = 0; i < n; i ++ ) {
        std::cin >> v[i];
        for (int j = 0; j < 33; j ++ ) {
            if (v[i] >> j & 1 ) {
                nums[j] += n - i;
            }
        }
    }

    int now = n;

    i64 ans = 0;

    const int P = 1e9 + 7;

    for (int i = 0; i < n; i ++ ) {
        now --;
        for (int j = 0; j < 33; j ++ ) {
            if (v[i] >> j & 1) {
                nums[j] -= n - i;
                ans += (1LL << j) * ((now + 1) * now / 2 - nums[j]) % P * (i + 1) % P;
            } else {
                ans += (1LL << j) * nums[j] % P * (i + 1) % P;
            }
            ans %= P;
        }
    }
    std::cout << ans << "\n";
}