在具有特殊条件的集合中获得最大数量

Question

我最近遇到了一个问题，我很难找到答案。 这是一道题：

考虑一组 numbers.There 是树种输入：

1 x
2 x
3

第一个命令将整数 x 添加到集合中。第二个表示对于列表中的每个元素 y，输入：

y = y xor x

and 最后一个命令打印集合中最大的数字。例如：

结果：

0
7
15

如果 n 是输入的命令数： $1 \leq n\leq 500000$
和： $1 \leq x\leq 10^{9}$
还有1秒的执行时间限制！

目前我的解决方案：让我们调用集合 S 并有一个整数 m 最初是 0.as 你知道的：

number = number xor x xor x

意思是如果我们在某物上应用xor两次，那么它的效果是相反的，原始数字不会改变。也就是说，如果我们每次插入一个数字（命令 1），我们都会执行以下操作：

y = y xor m
add y to S

每次我们想从集合中得到一个数字：

find y
y = y xor m
return y

如果命令二出现以下情况：

m = m xor x

那么问题就差不多解决了，因为最初保存了数字的异或版本，需要时我们进行反转！但是这里的问题是找到集合中最大的数字（注意集合中的数字与原始数字不同）所以命令 3 正确。我不知道如何高效地做到这一点 time.but 我在这里有一个想法：
如果我们首先将集合中数字的二进制表示保存在 trie 数据结构中，也许我们可以快速找到最大的数字。我真的不知道我是怎么想到这个主意的。所以总结这些是我的问题：

问题 1:
如何在修改后的列表中找到最大的数字
问题2：
这个 trie 想法 好吗？
问题 3:
我如何在代码中实现它（这里的语言不是很重要）以便它在查找时工作？

还有首先解决这个问题所需的时间复杂度是多少？

感谢阅读我的问题。

Answer 1

是的，你的想法是正确的，它可以使用二进制 trie 数据结构在 O(N log 10^9) 中解决。

我们的想法是以二进制表示法存储数字，但将最大的位放在第一位，因此在遍历 trie 时我们可以选择导致最大答案的分支。

为了确定选择哪个分支，我们可以一点一点地确定，如果从某个 trie 节点我们有 2 个值为 0 和 1 的分支，我们选择在与 m

异或后给出更好结果的分支

示例代码（C++）：

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

int Trie[4000005][2];
int nxt = 2;

void Add(int x)
{
    bitset<32>b(x);
    int c = 1;

    for(int j=31; j>=0; j--)
        if(Trie[c][b[j]])c=Trie[c][b[j]];
    else c = Trie[c][b[j]] = nxt++;
}

int Get(int x)
{
    bitset<32>b(x),res(0);
    int c = 1;

    for(int j=31; j>=0; j--)
        if(Trie[c][!b[j]])c=Trie[c][!b[j]],res[j]=!b[j];
    else c = Trie[c][b[j]], res[j]=b[j];

    return res.to_ullong()^x;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int q,m=0;
    cin>>q;
    Add(0);

    while(q--)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int x;
            cin>>x;
            Add(x^m);
        }
        else if(type==2)
        {
            int x;
            cin>>x;
            m^=x;
        }
        else cout<<Get(m)<<"\n";
    }
}

Answer 2

这与非常相似，应该可以在 O(n) 中解决，因为 x 的位数是常数（对于 10^9，您必须查看30 个最低位）。

开始时 m = 0，每次遇到第二条命令时，您都会执行 m ^= x (m = m xor x).
使用二叉树。与链接的问题不同，桶中的数字数量并不重要，您只需要能够判断是否有一个数字的某个位为 1 或 0。例如。对于 3 位数字 1、4 和 5，树可能如下所示（左边表示位为 0，右边表示位为 1）：
```
     *
   /   \
  1     1   there are numbers with highest bit 0 and 1
 /      /
1      1    of the numbers with 1st bit 0, there is a number with 2nd bit 0 and ...
 \    / \
  1  1   1  of the numbers with 1st and 2nd bit 0, there is a number with 3rd bit 1,...
  1  4   5  (the numbers just to clarify)
```
所以加一个数就是加一些边和节点。
要获得集合中的最大数字，您沿着树向下并通过 m 的位并计算最大值 x，如下所示：
1. 初始化节点n作为树的根，i = 29我们正在看的m的位和解x = 0。
2. mi = (m & (1 << i)) >> i（如果 m 中的位为 1，则为 1，否则为 0）。
  1. 如果我们查看 n 并且只有一条表示 0 的边，或者如果 mi == 1 并且我们有一条 0 边：n 成为由该边连接的节点，x = 2 * x + mi（或更花哨的：x = (x << 1) | mi）。
  2. 否则n成为1边连接的节点，x = 2 * x + 1 - mi
3. 如果 i > 0：将 i 减 1 并继续第 2 步。

3位数m = 6（110）和集合中的数字1（001），4（100）和5（101）的例子，答案应该是7（111），即1 xor 6: 第一步我们向左走并且x = 1，然后我们只能向左走并且x = 3，然后我们只能向右走并且x = 7.

在具有特殊条件的集合中获得最大数量

geting maximum number in a set with special conditions

algorithm

data-structures

set

xor