网站建设亿玛酷神奇5,看动漫什么网站好,建站如何挣钱,河北建投商务网电子招标采购平台Beautiful Subarrays#xff1a;
题目大意: 思路解析#xff1a;
要找到一个区间并且区间的l--r里面所有的元素异或值大于等于k#xff0c;称这样的数组是优美子数组#xff0c;问优美子数组有多少个。
[L,R] 的数组异或和等价于 (a1,a2,a3,....aL-1) ^ (a1,a2,a3,a4,..… Beautiful Subarrays
题目大意: 思路解析
要找到一个区间并且区间的l--r里面所有的元素异或值大于等于k称这样的数组是优美子数组问优美子数组有多少个。
[L,R] 的数组异或和等价于 (a1,a2,a3,....aL-1) ^ (a1,a2,a3,a4,....aR)那么发现我们可以用前缀和的思想来找到一个前缀使得[L,R]是优美子数组发现这种二进制的寻找可以利用字典树实现然后每次在这样的字典树插入前缀。
寻找时如果加上当前位就能大于等于k那么我们并不用关心以后的情况了直接加上满足能加上当前位的所有情况即可这里需要利用一个标记位进行预处理。
代码实现 #include bits/stdc.h
using namespace std;
#define ll long long
const int maxn 3e7 5;
int ch[maxn][2];
int tag[maxn];
int tot 0;
ll ans 0;
int k;
void insert(int x){int p 0;tag[p];for (int i 30; i 0; i--) {int c (x i) 1;if (ch[p][c] 0) ch[p][c] tot;p ch[p][c];tag[p];}
}void get(int x){int cur 0;int p 0;for (int j 30; j 0; j--) {int c (x j) 1;if ((cur | (1 j)) k){ans ch[p][c ^ 1] ! 0 ? tag[ch[p][c ^ 1]] : 0;p ch[p][c];}else {cur | (1 j);p ch[p][c ^ 1];}if (p 0) break;}if (cur k) ans p ! 0 ?tag[p]:0;
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);memset(ch, 0, sizeof(ch));memset(tag, 0, sizeof(ch));int n;cin n k;int s 0;insert(s);for(int i 0; i n; i){int num;cin num;s ^ num;get(s);insert(s);}cout ans endl;return 0;
}
