【算法新题】TJOI2017-异或和

题目内容

原题链接

给定一个长度为 n n n 的整数数组 a a a ，问所有子数组和的异或和是多少。

数据范围

1 ≤ n ≤ 1 0 5 1\leq n\leq 10^5 1≤n≤105 ∑ a i ≤ 1 0 6 \sum a_i\leq 10^6 ∑ai​≤106

题解 基本思路

本题是 ARC092D - Two Sequences 的同类型题，ARC092D 中是两个数和的异或和，而本题是两个数差的异或和。

子数组的和，自然会想到前缀和，考虑 p r e i pre_i prei​ 和 p r e j pre_j prej​ ， j < i j<i j<i ，那么子数组 a j + 1 , a j + 2 , ⋯   , a i a_{j+1},a_{j+2},\cdots,a_i aj+1​,aj+2​,⋯,ai​ 的和为 p r e i − p r e j pre_i-pre_j prei​−prej​

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

考虑和的第 k k k 位， x = p r e i   m o d   2 k + 1 , y = p r e j   m o d   2 k + 1 x=pre_i\bmod 2^{k+1},y=pre_j\bmod 2^{k+1} x=prei​mod2k+1,y=prej​mod2k+1

x ≥ y x\geq y x≥y ，考虑 x − y x-y x−y 的第 k k k 位是否为 1 1 1 x < y x<y x<y ，因为 p r e i ≥ p r e j pre_i\geq pre_j prei​≥prej​ ，所以可以将 2 k + 1 2^{k+1} 2k+1 添加到 x x x 上 判断 x + 2 k + 1 − y x+2^{k+1}-y x+2k+1−y 的第 k k k 位是否为 1 1 1 。

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

优化

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

以 k = 2 k=2 k=2 为例，区间和为 [ 010 0 2 , 011 1 2 ] [0100_2,0111_2] [01002​,01112​] 以及 [ 110 0 2 , 111 1 2 ] [1100_2,1111_2] [11002​,11112​] 的区间是满足条件的。

[ 010 0 2 , 011 1 2 ] [0100_2,0111_2] [01002​,01112​] 对应的 p r e j pre_j prej​ 范围是 [ x − 011 1 2 , x − 010 0 2 ] [x-0111_2,x-0100_2] [x−01112​,x−01002​] [ 110 0 2 , 111 1 2 ] [1100_2,1111_2] [11002​,11112​] 对应的 p r e j pre_j prej​ 范围是 [ x − 111 1 2 , x − 110 0 2 ] [x-1111_2,x-1100_2] [x−11112​,x−11002​]

显然这些区间都不能为负数，所以我们需要额外判断，对于 p r e i ≥ 2 k + 1 pre_i\geq 2^{k+1} prei​≥2k+1 的 x x x ，就给他们加上 2 k + 1 2^{k+1} 2k+1 。

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

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

代码 #include <bits/stdc++.h> 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; } 一样的题，更大的数据范围

灵茶八题 - 子数组 +w^