合肥网站建设晨飞,wordpress seo链接,wap网站不流行,免费邮箱登录163登录题目内容 原题链接 给定一个长度为 n n n 的整数数组 a a a #xff0c;问所有子数组和的异或和是多少。
数据范围 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 的同类型…题目内容 原题链接 给定一个长度为 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 ji ji 那么子数组 a j 1 , a j 2 , ⋯ , a i a_{j1},a_{j2},\cdots,a_i aj1,aj2,⋯,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 xpre_i\bmod 2^{k1},ypre_j\bmod 2^{k1} xpreimod2k1,yprejmod2k1 x ≥ y x\geq y x≥y 考虑 x − y x-y x−y 的第 k k k 位是否为 1 1 1 x y xy xy 因为 p r e i ≥ p r e j pre_i\geq pre_j prei≥prej 所以可以将 2 k 1 2^{k1} 2k1 添加到 x x x 上 判断 x 2 k 1 − y x2^{k1}-y x2k1−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 k2 k2 为例区间和为 [ 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^{k1} prei≥2k1 的 x x x 就给他们加上 2 k 1 2^{k1} 2k1 。
用树状数组来维护区间内数的个数。
时间复杂度 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^
