当前位置:网站首页>【集训DAY4】异或【字典树】
【集训DAY4】异或【字典树】
2022-08-09 22:35:00 【VL——MOESR】
思路:
用一个trie,如果当前是位k是0,那就把1的答案加上,然后往0走。如果为1,那就往1走。
c o d e code code
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 2e7 + 10;
int n, k;
long long ans;
int s[MAXN];
int tir[MAXN][2], tot = 1, v[MAXN];
void add(int x) {
int u = 0;
for(int i = 30; i >= 0; i --) {
int g = (x >> i) & 1;
if(!tir[u][g])
tir[u][g] = ++ tot;
u = tir[u][g];
v[u] ++;
}
}
int query_(int x) {
int u = 0, ans1 = 0, sum = 0;
for(int i = 30; i >= 0; i --) {
int g = (x >> i) & 1;
if(sum + (1 << i) >= k) {
ans1 += v[tir[u][g ^ 1]];
u = tir[u][g];
}
else u = tir[u][g ^ 1], sum += (1 << i);
if(!u) break;
}
return ans1;
}
int main() {
scanf("%d%d", &n, &k);
add(0);
for(int i = 1; i <= n; i ++) {
int x;
scanf("%d", &x);
s[i] = s[i - 1] ^ x;
ans += query_(s[i]);
add(s[i]);
}
printf("%lld", ans);
return 0;
}
边栏推荐
- YGG 经理人杯总决赛已圆满结束,来看看这份文字版总结!
- 完全背包理论
- Gartner's global integrated system market data tracking, hyperconverged market growth rate is the first
- 金仓数据库 KingbaseGIS 使用手册(6.3. 几何对象创建函数)
- ElasticSearcch集群
- Explore the TiDB Lightning source code to solve the found bugs
- Redis集群
- MVC与MVVM模式的区别
- MQTT X Web:在线的 MQTT 5.0 客户端工具
- 数据库优化 | 干货
猜你喜欢
随机推荐
tiup cluster start
你的手机曾经被监控过吗?
上海一科技公司刷单被罚22万,揭露网络刷单灰色产业链
国内十大活跃报表 BI 产品深度对比及点评
Live Preview | ICML 2022 11 first-author scholars share online neural network, graph learning and other cutting-edge research
shader学习笔记(五)
一体化伺服电机在三轴钻孔机中的应用
Gold Warehouse Database KingbaseGIS User Manual (6.2. Management Functions)
测试2年,当时身边一起入行的朋友已经月薪20k了,自己还没过万,到底差在了哪里?
tiup cluster upgrade
Explore the TiDB Lightning source code to solve the found bugs
什么是平面文件数据库? 如何导入多种格式的文件:DSV、JSON、XML?
Snap: 322. Change of Change
了解什么是架构基本概念和架构本质
数据库优化 | 干货
String类常用方法
力扣:474.一和零
JS基础笔记-关于对象
Controller层代码这么写,简洁又优雅!
A Shanghai technology company was fined 220,000 for brushing orders, exposing the gray industry chain of online brushing