[热身赛]

//观察时间复杂度，肯定要拆位
//分析每一位的贡献，对abit二分符合b的bit
//对于这一位bit，要考虑a和b加后bit这一位会不会增加1，把会的区间枚举出来
//为了来处a本身这一位的影响，我们考虑a小于的bit的位的大小和b中小于等于bit位的//大小，二分出加后会进位到bit（有些停留待bit-1，有些超到了bit+1）的区间（也就//是个数）；然后根据a本身bit这一位是不是有1和和前面的区间，咳咳最多能保留出多//少个1，当a全部计算完毕后看奇偶就可以了
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N], b[N];
int n, sum;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    for (int bit = 0; bit <= 31; bit++) { 
        vector<int> tp;
        int e = 1LL << bit; 
        int mod = e <<1;    
        for (int j = 1; j <= n; j++) {
            tp.push_back(b[j] % mod); 
        }
        sort(tp.begin(), tp.end());

        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            int v = a[j] % e; 
            // 寻找区间 [e - v, 2e - v)
            int lower = e - v;
            int upper = mod - v;
            auto l = lower_bound(tp.begin(), tp.end(), lower);
            auto r = lower_bound(tp.begin(), tp.end(), upper);
            int len = max((int)0, (int)(r - l));

            if ((a[j] >> bit) & 1) { 
                cnt += (n - len);    
            } else {                 
                cnt += len;          
            }
        }
        if (cnt % 2) sum += e; 
    }
    cout << sum << "\n";
    return 0;
}

上述代码是小帅哥的思路，以下是数学的推导

采用二进制优化

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (auto &x : a) cin >> x;
        for (auto &x : b) cin >> x;

        int res = 0;
        // 按二进制每一位独立处理
      vector<int> a0, a1, b0, b1;
        for (int k = 0; k <= 30; k++) {
            a1.clear();
           a0.clear();
           b1.clear();
           b0.clear();

            int mask = (1 << k) - 1;  // 低k位的掩码

            // 预处理a数组的当前位和低k位
            for (auto x : a) {
                int bit = (x >> k) & 1;
                int low = x & mask;
                (bit ? a1 : a0).push_back(low);
            }
            // 预处理b数组的当前位和低k位
            for (auto x : b) {
                int bit = (x >> k) & 1;
                int low = x & mask;
                (bit ? b1 : b0).push_back(low);
            }

            // 对低k位排序以进行二分查找
            sort(a0.begin(), a0.end());
            sort(a1.begin(), a1.end());
            sort(b0.begin(), b0.end());
            sort(b1.begin(), b1.end());

            // 统计满足条件的对数，注意指定返回类型为 long long
            auto count = [&](const vector<int>& vec, int y, bool ge) -> long long {
                if (vec.empty()) return 0LL;
                if (ge)
                    return static_cast<long long>(vec.end() - lower_bound(vec.begin(), vec.end(), y));
                else
                    return static_cast<long long>(upper_bound(vec.begin(), vec.end(), y) - vec.begin());
            };

            // 计算进位为0时的有效对数
            long long cnt0 = 0;
            // a0与b1组合：当前位不同且低位和 < 2^k
            for (auto x : a0) {
                int rem = (1 << k) - x - 1;
                if (rem >= 0) cnt0 += count(b1, rem, false);
            }
            // a1与b0组合：当前位不同且低位和 < 2^k
            for (auto x : a1) {
                int rem = (1 << k) - x - 1;
                if (rem >= 0) cnt0 += count(b0, rem, false);
            }

            // 计算进位为1时的有效对数
            long long cnt1 = 0;
            // a0与b0组合：当前位相同且低位和 ≥ 2^k
            for (auto x : a0) {
                int need = (1 << k) - x;
                cnt1 += count(b0, need, true);
            }
            // a1与b1组合：当前位相同且低位和 ≥ 2^k
            for (auto x : a1) {
                int need = (1 << k) - x;
                cnt1 += count(b1, need, true);
            }

            // 若总有效对数为奇数，则当前位为1
            if ((cnt0 + cnt1) % 2 == 1)
                res |= (1 << k);
        }
        cout << res << "\n";
    return 0;
}

数学角度理解拆位

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n;
int f[40][40][3][3];
int inv[65];
signed main(){
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];

for(int i=0;i<n;i++){
for(int j=0;j<=31;j++){
for(int k=0;k<=31;k++){
f[j][k][(a[i]>>j)&1][(a[i]>>k)&1]++;
}
}
}
    inv[0]=1;
    for(int i=1;i<64;i++){
    inv[i]=(inv[i-1]<<1)%mod;
    }
    int ans=0;
    for(int j=0;j<=31;j++){
    for(int k=0;k<=31;k++){
    for(int a=0;a<=1;a++){
    for(int b=0;b<=1;b++){
    ans=(ans+inv[k+j]*f[j][k][a][b]*f[j][k][a^1][b^1]%mod)%mod;
    }
    }
    }
    }
    cout<<ans;


}

蓝桥异或板子（本质上是前缀异或贡献加拆位）

同时这道题如果不是求一段区间而是求任意两个数，那么直接采用上一题的数学公式拆分
然后打表成f【第i位】【0/1】的个数

可以考虑从二进制的本质入手，不如将其每一位数都拆开，去统计1的个数和0的个数，只有1的个数为奇数的时候，这一位才能计算贡献，我们从上面的异或操作性质已经发现，我们要找到一段区间有贡献，实际上就是去算两个点上的异或，所以我们只需要保证其中一个点是1，一个点是0即可，那么我们就可以得到最终的结果，1的数量乘以0的数量*此位的贡献值即可得到最终的结果（一段区间的贡献采用前缀）
for(int i=0;i<=20;i++)
    {
        cnt1=0;
        cnt0=1;//请思考此处为什么是1；
        //对于01，其实是1，01，两种方法
        for(int j=1;j<=n;j++)
        {
            if((a[j]>>i)&1)
            {
                cnt1++;
            }
            else
            {
                cnt0++;
            }
        }
        ans+=cnt1*cnt0*(1<<i);
}

上题中提到的一对的计算，但是是所有的子数组（加权）

//首先对于每个数字（这里都是指位下的数）
//包含他的数组在右边就是n-j；左边就是i+1；
//所以sum1（i）=sum1（i+1）+当前位是1*（n-j）
//当计算到当前这一位，就会有（i+1）*sum（i）的贡献，类似于下面的树形来实时计算；
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    long long total = 0;
    for (int k = 0; k <= 30; ++k) { // 处理每个二进制位
        vector<int> b(n);
        for (int i = 0; i < n; ++i) 
            b[i] = (a[i] >> k) & 1; // 提取第k位

        vector<long long> sum0(n+2, 0), sum1(n+2, 0);
        for (int i = n-1; i >= 0; --i) { // 预处理后缀和
            sum0[i] = sum0[i+1] + (b[i] == 0 ? (n - i) : 0);
            sum1[i] = sum1[i+1] + (b[i] == 1 ? (n - i) : 0);
        }

        long long cnt = 0;
        for (int i = 0; i < n; ++i) { // 累加贡献
            if (b[i] == 0) 
                cnt = (cnt + (i+1) * sum1[i+1]) % MOD;
            else 
                cnt = (cnt + (i+1) * sum0[i+1]) % MOD;
        }
        total = (total + cnt * ((1LL << k) % MOD)) % MOD;
    }
    cout << total % MOD << "\n";
    return 0;
}

类似于上述代码求加权，蓝桥pro，对于这个加权，只需要适当的枚举区间+神奇的减法

//为什么一个要哨兵，一个不要呢，为什么第二个代码wa一半

//ai版赏心悦目
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int ans = 0;
    for (int bit = 0; bit < 32; ++bit) { // 修正1: 0-based遍历
        vector<int> pre_xor(n + 1, 0);
        // 计算前缀异或的bit位
        for (int i = 1; i <= n; ++i)
            pre_xor[i] = pre_xor[i - 1] ^ ((a[i] >> bit) & 1);

        int cnt[2] = {1, 0}; // 初始前缀0的计数
        int sum[2] = {0, 0}; // 初始前缀0的位置和
        int res = 0;

        for (int r = 1; r <= n; ++r) { // r为右端点
            int curr = pre_xor[r];
            int target = curr ^ 1; // 需要找的前缀异或值

            // 贡献公式: Σ (r - l) = r*cnt[target] - sum[target]
            res = (res + (r * cnt[target] - sum[target])) % mod;

            // 更新当前前缀状态
            cnt[curr] = (cnt[curr] + 1) % mod;
            sum[curr] = (sum[curr] + r) % mod;
        }
        ans = (ans + (res * (1LL << bit)) % mod) % mod;
    }
    cout << (ans % mod + mod) % mod << endl; // 处理负数
    return 0;
}
//我的不断debug版（需要有哨兵）
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+10, mod = 998244353;
int a[N];
int b[N];
int sur1[N], sur0[N];
int s1[N], s0[N];
int n;
int ans = 0;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for (int i = 0; i <= 31; i++){
        b[n+1] = 0;
        for (int j = n; j >= 1; j--){
            b[j] = (((a[j] >> i) & 1) ^ b[j+1]);
        }
        sur1[n] = (b[n] ? 1 : 0);
        sur0[n] = (b[n] ? 0 : 1);
        s1[n] = (b[n] ? 1 : 0);
        s0[n] = (b[n] ? 1 : 2);//哨兵

        for (int j = n - 1; j >= 1; j--){
            if(b[j]){
                sur1[j] = (n - j+1); 
                s1[j] = 1;
                s0[j] = 0;
                sur0[j] = 0;
            } else {
                sur0[j] = (n - j+1); 
                s0[j] = 1;
                s1[j] = 0;
                sur1[j] = 0;
            }
            sur1[j] += sur1[j+1];
            sur0[j] += sur0[j+1];
            s1[j] += s1[j+1];
            s0[j] += s0[j+1];
        }
        int e = (1 << i)%mod;

        for (int j = 1; j <= n; j++){
            if(b[j]){
                ans = (ans + e * (s0[j] * (n - j + 1)%mod - sur0[j])%mod+mod) % mod;
            } else {
                ans = (ans + e * (s1[j] * (n - j + 1)%mod - sur1[j])%mod+mod) % mod;
            }
        }
    }
    cout << ans;
    return 0;
}

与蓝桥异或异曲同工的树形结合

//巧妙的是以某个树节点为根去计算所有的子节点
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll dp[N][2];
ll a[N];
ll ans = 0;
vector<int> G[N];
void dfs(int cur, int fa, int bit)
{
    ll res = 0;
    int b = (a[cur] >> bit) & 1;//取得当前的a[cur]在第bit位是0还是1
    //这里好巧妙啊... 
    dp[cur][b] = 1;//初始化
    dp[cur][b ^ 1] = 0;//初始化

    for(auto v:G[cur]){
        if(v!=fa){
            dfs(v, cur, bit);
            //间接枚举出所有的区间
            res += dp[cur][0] * dp[v][1] + dp[cur][1] * dp[v][0];//统计子节点到cur的路径上异或和，只需算1^0与0^1即可
            之后在加
            dp[cur][b ^ 0] += dp[v][0];//更新异或操作后的状态值
            dp[cur][b ^ 1] += dp[v][1];//更新异或操作后的状态值
        }
    }   

    ans += (res << bit);//更新答案
}
int main()
{
    int n, u, v;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        ans += a[i];
    }
    for (int i = 0; i<n - 1; i++){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    //由于权值最大为1e6，所以只需要枚举到20位。2^20=1048576 
    for (int i = 0; i <= 20; i++)
        dfs(1, 0, i);

    cout<<ans<<"\n";
}

水体，二分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int a[N],pre[N][32];
int l,k;
int n;
bool check(int mid){
    int sum=0;
    for(int i=0;i<=31;i++){
        int bit=pre[mid][i]-pre[l-1][i];
        if(bit==0){
            sum+=(1<<i);
        }
    }
    return sum>=k;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int q;
    cin>>q;
    for(int i=0;i<=31;i++){
        if(!(a[1]>>i&1))
        pre[1][i]=-1;
        else pre[1][i]=0;
        for(int j=2;j<=n;j++){
            int bit=(a[j]>>i)&1;
            if(bit)
            pre[j][i]=pre[j-1][i];
            else
            pre[j][i]=pre[j-1][i]-1;
        }
    }
    while(q--){
        cin>>l>>k;
        int a=l,b=n;
        while(a<=b){
            int mid=(a+b)/2;
            if(check(mid)){
                a=mid+1; 
            }else{
                b=mid-1;
            }
        }
       int sum=0;
        for(int i=0;i<=31;i++){
        int bit=pre[b][i]-pre[l-1][i];
        if(bit==0){
            sum+=(1<<i);
        }
        }
        if(sum>=k) cout<<b<<" ";
        else cout<<-1<<" ";
    }
    cout<<"\n";
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        solve();
    }

}

待