查找异或集合中的最大数量

Question

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

考虑一组数字。有树的输入形式：

1 x
2 x
3

第一个命令将整数x添加到集合中。第二个意味着对列表中的每个元素y放置：

y = y xor x

and最后一条命令将打印出该组中最大的数字。例如：

10
3
1 7
3
2 4
2 8
2 3
1 10
1 3
3
2 1

结果：

0
7
15

如果n是输入中的命令数：

到目前为止，我的解决方案：让我们调用集合S并具有一个整数m，该整数最初为0。如您所知：

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

然后问题几乎解决了，因为最初保存数字的XORed版本，并且在需要时我们做相反的操作！但是这里的问题是找到集合中的最大数字（请注意集合中的数字与原始数字不同），因此命令3可以正常工作。我不知道如何在有效时间内完成此操作。但是我有一个主意：如果首先将数字的二进制表示形式保存在集合中的[[trie数据结构中，也许我们可以很快找到最大的数字。我真的不知道怎么回事，但是这个主意发生在我身上。总结一下，这就是我的问题：

问题1：

如何在修订后的列表中找到最大的数字问题2：这个trie idea好吗？问题3：我该如何在代码中实现它（这里的语言不是很重要），以便可以在时间找到它？首先解决这个问题还需要多少时间？

感谢您阅读我的问题。

Answer 1

是的，您的想法是正确的，可以使用二进制特里数据结构在O（N log 10 ^ 9）中解决。

想法是将数字存储为二进制表示法，但将最大位放在首位，因此在遍历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

这与this problem非常相似，应该可以在O（n）中解决，因为x的位数是恒定的（对于10 ^ 9，您将不得不查看最低的30位）。

1. 在开始m = 0时，每次遇到第二条命令时，您都会执行m ^= x（m = m xor x）。
2. 使用二叉树。与链接的问题不同，存储桶中的数字无关紧要，您只需要知道是否存在某个位数为一或为零的数字即可。例如。对于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)

   所以添加数字仅意味着添加一些边和节点。

3. 要获得集合中的最高数字，请沿着树向下穿过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]连接的节点>

      如果i > 0：将i减1，然后继续执行步骤2。

[3位数字m = 6（110）以及数字1（001），4（100）和5（101）的示例，答案应为7（111），即1 x或6：第一步，我们左移x = 1，然后我们只能左移x = 3，然后我们只能右移x = 7。