Luogu P3760 [TJOI2017]异或和

题目描述

https://www.luogu.com.cn/problem/P3760

简要题意：给定一个长度为 $n$ 的序列 $a_i$，求所有子区间的和的异或和

$n\le 10^5,\sum a \le 10^6$

Solution

将区间和变成前缀和相减，然后按位考虑

假设现在在考虑第 $k$ 位，我们把包括第 $k$ 位在内的高位都扔掉

然后我们考虑 $x - y$

如果 $x$ 的第 $k$ 位是 $1$，那么 $y$ 的 $k$ 位是 $1$ 且 $x<y$ 或 $y$ 的第 $k$ 位是 $0$ 且 $x\ge y$ 才能保证 $x-y$ 的第 $k$ 位是 $1$ ​

$x$ 的第 $k$ 位是 $0$ 的情况正好相反

这个大小关系可以用树状数组维护，时间复杂度 $O(n\log^2 \sum a_i)$

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100010
#define Maxn 1000010
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, s[maxn];

struct Bit {
    int Bit[Maxn], n;

    void add(int i, int v) { ++i; while (i <= n) Bit[i] += v, i += lowbit(i); }

    int get_sum(int i) {
        int s = 0; ++i; 
        while (i) s += Bit[i], i -= lowbit(i);
        return s;
    }

    void clear() { memset(Bit, 0, sizeof Bit); } 
} B[2];

int ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        s[i] = s[i - 1] + x;
    } B[0].n = B[1].n = s[n] + 1; 
    for (int o = 0; o <= 20; ++o) {
        int sum = 0, sz[2] = { 0, 0 }; B[0].clear(); B[1].cl	ear(); 
        for (int i = 0; i <= n; ++i) {
            int d = s[i] >> o & 1, v = s[i] & (1 << o) - 1; 
            sum += sz[d] - B[d].get_sum(v) + B[d ^ 1].get_sum(v);
            B[d].add(v, 1); sz[d]++; 
        } ans += (1 << o) * (sum & 1); 
    } cout << ans << "\n"; 
    return 0;
}