L - Choosing The Commander（01字典树）

59 阅读 0 评论 39 点赞

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

概述

CodeForces - 817E

题意：有 $n$ 次操作，每次有三种选择：


1、插入一个数x
2、删除一个数x
3、给定两个数p，l，查询所有x，统计所有满足 p ^ x < l 的 x 的数量

思路：因为异或且需查询所有已经存在的 $x$ ，考虑 01 字典树，将每一个数的二进制位（从高到低）往树中插入或删除

对于操作 3（查询）：

对 $p, l$ 一起从二进制高位往低位遍历，用 $c_1$ 记录 $p$ 的第 $i$ 位二进制， $c_2$ 记录 $l$ 第 $i$ 位二进制，用 $c_3$ 记录所有 $x$ 的第 $i$ 位二进制

有如下几种情况：（每步 $c_3$ 都有 0 1 两种情况，都需考虑）

1、 $c_1 = 1, c_2 = 1$ ：

① $c_3 = 1，c_1 xor c_3 = 1 xor 1 = 0 < c_2 = 1$ ，已经满足条件，所以对答案贡献为 $c_3 = 1$ 的数量，对于接下来的走法，走子节点1 或走子节点0 无论怎么取都已经符合条件，所以不用再往下走了，可以转向 $c_3 = 0$

② $c_3 = 0，c1 xor c_3 = 1 xor 0 = 1 == c_2 = 1$ ，还无法判断是否符合，所以继续往下找子节点，即 $p = t r i e [p] [0]$

2、 $c 1 = 1, c 2 = 0$ ：

① $c_3 = 1， c_1 xor c_3 = 0 == c_2 = 0$ ，还无法判断是否符合，所以继续往下找，即 $p = t r i e [p] [1]$

② $c_3 = 0，c_1 xor c_3 = 1 > c_2 = 0$ ，已经不符合，不需要再考虑

3、 $c_1 = 0, c_2 = 1$ ：

① $c_3 = 1，c_1 xor c_3 = 1 == c_2 = 1$ ，无法判断是否符合，所以继续往下找子节点，即 $p = t r i e [p] [1]$

② $c_3 = 0，c_1 xor c_3 = 0 < c_2 = 1$ ，已经满足条件，所以对答案贡献为 $c_3 = 0$ 的数量,对于接下来的走法，走子节点1 或走子节点0 无论怎么取都已符合条件，所以不用再往下走了，可以转向 $c_3 = 1$

4、 $c_1 = 0, c_2 = 0$ ：

① $c_3 = 1，c_1 xor c_3 = 1 > c_2 = 0$ ，已经不符合，不需要再考虑

② $c_3 = 0，c_1 xor c_3 = 0 == c_2 = 0$ ，还无法判断是否符合，所以继续往下找子节点，即 $p = t r i e [p] [0]$

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define endl 'n'
#define ll long long
#define ull unsigned long long
#define mem(a, b) memset(a, b, sizeof a)
//#define int ll
#define pii pair<int,int>
#define all(a) a.begin(), a.end()
using namespace std;
#define dbg(x)

do

{

cout << #x << " -> "; 
err(x);

} while (0)
void err()
{
cout << endl;
}
template<class T, class... Ts>
void err(const T& arg, const Ts &... args)
{
cout << arg << ' ';
err(args...);
}
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 10;
const ll MOD = 1000003;
const double eps = 1e-4;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m, q;
ll trie[maxn << 5][2];
ll sum[maxn << 5];
int k = 1;
void insert(ll x)
{
ll p = 0;
for (int i = 31; i >= 0; i--)
{
int c = (x >> i) & 1;
if (!trie[p][c])
{
trie[p][c] = k;
k++;
}
p = trie[p][c];
sum[p]++;
}
}
void del(ll x)
{
ll p = 0;
for (int i = 31; i >= 0; i--)
{
int c = (x >> i) & 1;
if (!trie[p][c])
return;
p = trie[p][c];
sum[p]--;
}
}
ll search(ll x, ll y)
{
ll p = 0;
ll ans = 0;
for (int i = 31; i >= 0; i--)
{
ll c1 = (x >> i) & 1;
ll c2 = (y >> i) & 1;
if (c1 == 1)
{
if (c2 == 1)
{
ans += sum[trie[p][1]];
p = trie[p][0];
}
else
p = trie[p][1];
}
else
{
if (c2 == 1)
{
ans += sum[trie[p][0]];
p = trie[p][1];
}
else
p = trie[p][0];
}
if (!p)
break;
}
return ans;
}
void solve()
{
cin >> n;
int op;
while (n--)
{
cin >> op;
if (op == 1)
{
cin >> m;
insert(m);
}
else if (op == 2)
{
cin >> m;
del(m);
}
else
{
cin >> m >> q;
cout << search(m, q) << endl;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("mosalah.in", "r", stdin);
int t = 1;
//cin >> t;
while (t--)
solve();
return 0;
}