L - Choosing The Commander（字典树）

112 阅读 0 评论 74 点赞

我是靠谱客的博主单薄音响，最近开发中收集的这篇文章主要介绍L - Choosing The Commander（字典树），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem - 817E - Codeforces (Unofficial mirror site, accelerated for Chinese users)

题意：

有n次操作，共三种操作：

1：插入一个数x

2：删除一个数y

3：给定一个p和l，询问p 异或 x 小于l的x的数量（x需未被删除）

思路：

运用字典树，将每一个数的二进制位（从高到低）往树中插入或删除

询问（操作3）：

将 p 和 l 的二进制位从高到低遍历

若p当前位为 1 ：l当前位为1: 若x当前位为1， 1 ^ 1 = 0 < 1, 满足条件，加上x当前位为1的数量

若x当前位为0， 1 ^ 0 = 1, 则继续往下找

l当前位为0: 若x当前位为1， 1 ^ 1 = 0 == 0, 则继续往下找

若x当前位为0， 0 ^ 1 = 1 > 0, 不满足条件

若p当前位为 0 ：l当前位为1: 若x当前位为1， 0 ^ 1 = 1 == 1, 则继续往下找

若x当前位为0， 0 ^ 0 = 0 < 1, 满足条件，加上x当前位为0的数量

l当前位为0: 若x当前位为1， 0 ^ 1 = 1 > 0, 不满足条件

若x当前位为0， 0 ^ 0 = 0 == 0, 则继续往下找

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

const int N = 1e5 + 5;

ll n;

struct node {
	ll bit[2];//子节点对应的节点序号，若为0则代表子节点不存在
	ll cnt;//当前位置的权值
}tree[N << 5];
ll sz;//节点序号

void insert(ll num)
{
	ll p = 0;
	for (ll i = 31; i >= 0; i--)
	{
		if (!tree[p].bit[(num >> i) & 1])
			tree[p].bit[(num >> i) & 1] = ++sz;
		p = tree[p].bit[(num >> i) & 1];
		tree[p].cnt++;
	}
}

void del(ll num)
{
	ll p = 0;
	for (ll i = 31; i >= 0; i--)
	{
		if (!tree[p].bit[(num >> i) & 1])
			return;
		p = tree[p].bit[(num >> i) & 1];
		tree[p].cnt--;
	}
}

ll search(ll num1, ll num2)
{
	ll p = 0;
	ll ans = 0;
	for (ll i = 31; i >= 0; i--)
	{
		ll x = (num1 >> i) & 1;//p当前位的二进制
		ll y = (num2 >> i) & 1;//l当前位的二进制
		if (x == 1)/对应多种情况
		{
			if (y == 1)
			{
				ans += tree[tree[p].bit[1]].cnt;
				p = tree[p].bit[0];
			}
			else if (y == 0)
				p = tree[p].bit[1];
		}
		else if (x == 0)
		{
			if (y == 1)
			{
				ans += tree[tree[p].bit[0]].cnt;
				p = tree[p].bit[1];
			}
			else if (y == 0)
				p = tree[p].bit[0];
		}
		if (!p)//没有仍需要判断的点
			break;
	}
	return ans;
}

void solve()
{
	cin >> n;
	while (n--)
	{
		ll op;
		cin >> op;
		if (op == 1)
		{
			ll x;
			cin >> x;
			insert(x);
		}
		else if (op == 2)
		{
			ll x;
			cin >> x;
			del(x);
		}
		else
		{
			ll x, y;
			cin >> x >> y;
			cout << search(x, y) << 'n';
		}
	}
}

int main()
{
	solve();
	return 0;
}