const int MAXNODE = 100000;//单词数*单词长度(最坏情况下节点数量)
int tot, root; //初始 tot=root=1;
int son[MAXNODE + 5][10]; //字符集:'0'~'9'
int tag[MAXNODE + 5]; // 存在几个单词
//清空节点
void clearNode(int nId)
{
for (int i = 0; i < 10; i++)
son[nId][i] = 0;
tag[nId] = 0;
}
//字典树中插入字符串
void ins(const string &s)
{
int now = root;
for (int i = 0; i < s.size(); i++)
{
int j = s[i] - '0';
if (!son[now][j])
{
son[now][j] = ++tot;
clearNode(tot);
}
now = son[now][j];
}
tag[now]++;
}
把一个整数的 31 位二进制看做一个字符串,每一位上是 0/1
const int MAXNODE = 100000 * 31; // 单词数*单词长度(最坏情况下节点数量)
int tot, root, son[MAXNODE + 5][2];
void clearNode(int nId)
{
for (int i = 0; i < 2; i++)
son[nId][i] = 0;
tag[nId] = 0;
}
void ins(int s)
{
int now = root;
for (int i = 30; i >= 0; i--)
{
// s的2^i位是多少
int j = ((s >> i) & 1);
if (!son[now][j])
{
son[now][j] = ++tot;
clearNode(tot);
}
now = son[now][j];
}
}
int check(int s)
{
int res = 0;
int now = root;
for (int i = 30; i >= 0; i--)
{
int j = ((s >> i) & 1);
// 尽可能走不同的
if (son[now][1 - j])
{
res += (1 << i);
now = son[now][1 - j];
}
else
{
now = son[now][j];
}
}
return res;
}
namespace Trie
{
const int MAXNODE = 600000 * 33; //最多总节点数
int tot, son[MAXNODE + 5][2], tag[MAXNODE];
// 基于编号为 pre 的字典树,新加了 val 这个数,建立一个编号为 now 的字典树。
void insert(int now, int pre, int val)
{
for (int i = 30; i >= 0; i--)
{
tag[now] = tag[pre] + 1; // 在原版本的基础上更新
int j = ((val >> i) & 1);
if (j == 0)
{
son[now][0] = ++tot;
son[now][1] = son[pre][1];
now = son[now][0];
pre = son[pre][0];
}
else
{
son[now][0] = son[pre][0];
son[now][1] = ++tot;
now = son[now][1];
pre = son[pre][1];
}
}
tag[now] = tag[pre] + 1;
}
// 编号为 now 的树与编号为 pre 的树,作差后得到的新树上查找与 val 的最大异或和
int query(int now, int pre, int val)
{
int res = 0;
for (int i = 30; i >= 0; i--)
{
int j = ((val >> i) & 1);
// 尽量向不同的地方跳
if (tag[son[now][1 - j]] - tag[son[pre][1 - j]])
{
res += (1 << i);
now = son[now][1 - j];
pre = son[pre][1 - j];
}
else
{
now = son[now][j];
pre = son[pre][j];
}
}
return res;
}
}
const int MAXRT = 600000; //最多字典树棵数
int rt[MAXRT + 5];