当前位置:网站首页>【集训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;
}
边栏推荐
- && 不是此版本的有效语句分隔符
- Live Preview | ICML 2022 11 first-author scholars share online neural network, graph learning and other cutting-edge research
- What are the Shenzhen fortress machine manufacturers?Which one do you recommend?
- 【哲理】读书的意义
- Click: 518. Change Exchange II
- tiup cluster scale-out
- 力扣:279.完全平方数
- 伦敦银行情中短线的支撑和阻力位
- 多商户商城系统功能拆解25讲-平台端分销申请
- 【诗歌】被讨厌的勇气
猜你喜欢

Gartner's global integrated system market data tracking, hyperconverged market growth rate is the first

Explore the TiDB Lightning source code to solve the found bugs

了解什么是架构基本概念和架构本质

Live Preview | ICML 2022 11 first-author scholars share online neural network, graph learning and other cutting-edge research

2022-08-09 mysql/stonedb-子查询性能提升-概论

2020年度SaaS TOP100企业名单

Travel with Shengteng: See all the AI attractions in Jinling City in one day

32 JZOF 】 【 print down on binary tree

How to match garbled characters regularly?

完全背包理论
随机推荐
【云原生】一文讲透Kubevela addon如何添加腾讯Crane
测试2年,当时身边一起入行的朋友已经月薪20k了,自己还没过万,到底差在了哪里?
70. 爬楼梯进阶版
How to know the computer boot record?
34. Fabric2.2 证书目录里各文件作用
68. qt quick-qml multi-level folding drop-down navigation menu supports dynamic add/unload, support qml/widget loading, etc.
&& 不是此版本的有效语句分隔符
torch.distributed多卡/多GPU/分布式DPP(二)——torch.distributed.all_reduce(reduce_mean)&barrier&控制进程执行顺序&随机数种子
多线程是同时执行多个线程的吗
2022-08-09 mysql/stonedb-子查询性能提升-概论
Gartner全球集成系统市场数据追踪,超融合市场增速第一
什么是平面文件数据库? 如何导入多种格式的文件:DSV、JSON、XML?
完全背包理论
Day 12 of learning to program
[Cloud Native] This article explains how to add Tencent Crane to Kubevela addon
Redis集群
杭电多校-Counting Stickmen-(思维+组合数+容斥)
金仓数据库 KingbaseGIS 使用手册(6.4. 几何对象存取函数)
harbor配置远程仓库
SRv6性能测量