【算法新题】TJOI2017-异或和

考虑减法的特性，先考虑低位，低位不够了会向高位借位。

考虑和的第 $k$ 位，$x=pr{e}_i\mathrm{mod}{2}^{k+1},y=pr{e}_j\mathrm{mod}{2}^{k+1}$

• $x\ge y$ ，考虑 $x-y$ 的第 $k$ 位是否为 $1$
• $x<y$ ，因为 $pr{e}_i\ge pr{e}_j$ ，所以可以将 $2^{k+1}$ 添加到 $x$ 上
  判断 $x+2^{k+1}-y$ 的第 $k$ 位是否为 $1$ 。

这样的做法需要枚举 $i$ 和 $j$ ，时间复杂度是 $O(n^2)$ ，考虑如何优化。

优化

我们需要枚举 $i$ 的同时，找到所有满足条件的 $j$ 。

以 $k=2$ 为例，区间和为 $[0100_2,0111_2]$ 以及 $[1100_2,1111_2]$ 的区间是满足条件的。

• $[0100_2,0111_2]$ 对应的 $pr{e}_j$ 范围是 $[x-0111_2,x-0100_2]$
• $[1100_2,1111_2]$ 对应的 $pr{e}_j$ 范围是 $[x-1111_2,x-1100_2]$

显然这些区间都不能为负数，所以我们需要额外判断，对于 $pr{e}_i\ge 2^{k+1}$ 的 $x$ ，就给他们加上 $2^{k+1}$ 。

用树状数组来维护区间内数的个数。

时间复杂度：$O(20n\times \log 10^6)$ ，其中 $20$ 是值域对应的二进制数的最大位数，$\log 10^6$ 是树状数组单次操作的复杂度。

代码

#include 
using namespace std;

const int N = 100010;
const int MAX = 1000010;
const int BIT = 20;

int a[N];
int pre[N];
int tr[MAX];

void update(int p, int x, int limit) {
    p += 1;
    while (p <= limit) {
        tr[p] += x;
        p += p & -p;
    }
}

int query(int p) {
    p += 1;
    int res = 0;
    while (p > 0) {
        res += tr[p];
        p -= p & -p;
    }
    return res;
};

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

    int n;
    cin >> n;

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

    int ans = 0;
    for (int k = 0; k < BIT; ++k) {
        int mod = 1 << (k + 1);
        int mask = mod - 1;
        int limit = min(MAX - 1, mod);
        update(0, 1, limit);
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            int cur = pre[i] & mask;
            if (pre[i] >= mod) {
                cur += mod;
            }
            // L 是最小值，R 是最大值
            // cur 需要大于等于最小值，
            int L = 1 << k, R = (1 << (k + 1)) - 1;
            if (cur >= L) {
                int maxv = cur - L;
                int minv = max(0, cur - R);
                cnt ^= query(maxv) - query(minv - 1) & 1;
                L = 3 << k, R = (1 << (k + 2)) - 1;
                if (cur >= L) {
                    maxv = cur - L;
                    minv = max(0, cur - R);
                    cnt ^= query(maxv) - query(minv - 1) & 1;
                }
            }
            update(pre[i] & mask, 1, limit);
        }

        if (cnt) ans |= 1 << k;
        memset(tr, 0, sizeof(int) * (limit + 1));
    }

    cout << ans << "\n";

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

一样的题，更大的数据范围

灵茶八题 - 子数组 +w^