记一个01Trie板子

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 20;

int son[N * 31][2], cnt[N * 31];
int idx;

void insert(int x)
{
	int p = 0;
	for(int i = 30; i >= 0; -- i)
	{
		int u = x >> i & 1;
		if(!son[p][u]) son[p][u] = ++ idx;
		p = son[p][u];
		cnt[p] ++;	
	}	
}

int query(int x, int limit)
{
	int p = 0, res = 0;
	for(int i = 30; i >= 0; -- i)
	{
		int a = x >> i & 1, b = limit >> i & 1;
		if(b)
		{
			if(son[p][a]) res += cnt[son[p][a]];
			if(!son[p][a ^ 1]) return res;
			p = son[p][a ^ 1];
		}
		else
		{
			if(!son[p][a]) return res;
			p = son[p][a];
		} 
	}	
	res += cnt[p];
	return res;
}

int main()
{
	int __;
	scanf("%d", &__);
	while(__ -- )
	{
		int n, m;
		scanf("%d%d", &n, &m);
		idx = 0;
		memset(son, 0, sizeof son);
		memset(cnt, 0, sizeof cnt);
		for(int i = 1; i <= n; ++ i)
		{
			int x; scanf("%d", &x);
			insert(x);
		}
		while(m -- )
		{
			int x, l, r;
			scanf("%d%d%d", x ,l ,r);
			printf("%d\n", query(x, r) - query(x, l - 1)); 
		}
	} 
	return 0;
}

记一个01Trie板子

原文：https://www.cnblogs.com/popodynasty/p/14714220.html