异或和之和 | 前缀+位运算+奉献

(觉得这题很好就写了一下，有错可纠正QWQ)

题目：

思路：

由于n给的很大，我们如果直接暴力的话只能拿一半的分，以此考虑优化

观察数据可知最大为2的20次方，也就是说我们可以利用拆位奉献的思想优化

对于每个数字 A 我们可以写出他的二进制形式，假设如下

由于我们要求出所有L~R的异或和之和，那么通常的暴力时间复杂度过高，那我们必须得优化到将近线性的时间复杂度

我们先考虑第一位

我们可以参考前缀和的思想，我们将每位都存入一个01数组(这里叫S)中，这个数组用于储存从第1个数到第i个数的异或和，这样我们便可以快速求出从1到R之间的异或和之和了

计算公式即 (S[0] + S[1] + ... + S[n]) *  

但是当L不为1时我们该如何求解呢？ 

这里就要考察位运算的技巧了，假设我们需要求区间i~j的异或和，那么根据S数组，有

S[i] = a[0][0] ^ a[1][0] ^ a[2][0] ... ^ a[i-1][0] ^ a[i][0]   (a[i][0] 代表 第i个数的二进制位的第0位)

S[j] = a[0][0] ^ a[1][0] ^ a[2][0] ... ^ a[i-1][0] ^ a[i][0] ^ a[i+1][0] ... ^ a[j][0]

既然要i~j的异或和，那么就是要 a[i][0] ^ ... ^ a[j][0]  (假设这个为ANS)

由于相同两个数异或为0，任何数异或0都为它本身，那么有

S[j] ^ S[i-1] = ANS

由于异或有交换律，所以我们对比上式中的表达式两两消除即可

但是我们任然可以继续优化，由于只有当ANS为1时才对答案有奉献，所以对于S[j]，我们只需要考虑1~j中有多少个S[i]与S[j]不一样即可，即要满足S[i] = S[j] ^ 1

至此我们就将对于二进制的第i位求所有L~R区间异或和之和的步骤优化至近线性复杂度

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

ll a[100010][25];
//异或
//x ^ x = 0
// 1 ^ 0 = 1
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) 
    {
        int x;
        cin >> x;
        for (int j = 0; j <= 20; ++j)
        {
            a[i][j] = (x >> j) & 1;
            a[i][j] ^= a[i - 1][j];
        }
    }
    ll ans = 0;
    for (int j = 0; j <= 20; ++j) 
    {
        int m[2] = {0,0};
        m[0]++;//如果是第一位1的话，自身可以直接加上，即1 ^ 1 = 0，故0要初始为1
        for (int i = 1; i <= n; ++i) 
        {
            int x = m[a[i][j] ^ 1];
            ans += 1LL * (1LL << j) * x;
            m[a[i][j]]++;
        }
    }
    cout << ans << '\n';
}
int main()
{
    //cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}