当前位置:网站首页>【集训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;
}
边栏推荐
猜你喜欢
How to know the computer boot record?
中国SaaS企业排名,龙头企业Top10梳理
测试2年,当时身边一起入行的朋友已经月薪20k了,自己还没过万,到底差在了哪里?
SRv6 performance measurement
高手这样看现货白银走势图
kubesphere
IT传奇人物菲尔德的转型经验教训及给CIO的建议
安踏携手华为运动健康共同验证冠军跑鞋 创新引领中国体育
金仓数据库 KingbaseGIS 使用手册(6.4. 几何对象存取函数)
torch.distributed多卡/多GPU/分布式DPP(二)——torch.distributed.all_reduce(reduce_mean)&barrier&控制进程执行顺序&随机数种子
随机推荐
Mysql/stonedb - slow SQL - 2022-08-09 Q16 analysis
6款跨境电商常用工具汇总
A Shanghai technology company was fined 220,000 for brushing orders, exposing the gray industry chain of online brushing
[Cloud Native] This article explains how to add Tencent Crane to Kubevela addon
深圳堡垒机厂家有哪些?重点推荐哪家?
Basic operations of xlrd and xlsxwriter
集合运算样例
生成NC文件时,报错“未定义机床”
【实用工具系列】MathCAD入门安装及快速上手使用教程
金仓数据库 KingbaseGIS 使用手册(6.5. 几何对象编辑函数)
MVC与MVVM模式的区别
tiup cluster template
leetcode 20. Valid Parentheses 有效的括号(中等)
直播app开发搭建,flutter 实现自适应、自动换行、相对布局
金仓数据库 KingbaseGIS 使用手册(6.3. 几何对象创建函数)
【哲理】读书的意义
Gartner's global integrated system market data tracking, hyperconverged market growth rate is the first
2022-08-09 mysql/stonedb-慢SQL-Q16分析
函数习题(下)
【JZOF】77 Print binary tree in zigzag