当前位置:网站首页>【集训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;
}
原网站

版权声明
本文为[VL——MOESR]所创,转载请带上原文链接,感谢
https://blog.csdn.net/liuziha/article/details/126234722