algorithm - 在特殊条件下获取集合中的最大数量

Question

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

考虑一组数字。输入有树形类型:

1 x
2 x
3

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

y = y xor x

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

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

结果:

0
7
15

如果 n 是输入中的命令数:
和:
还有1秒的执行时间限制!

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

number = number xor x xor x

这意味着如果我们对某个东西应用两次异或，那么它的效果就会相反，并且原始数字不会改变。也就是说，如果我们每次插入一个数字(命令 1)，我们都会执行以下操作:

y = y xor m
add y to S

每次我们想从集合中获取一个数字时:

find y
y = y xor m
return y

如果命令二如下:

m = m xor x

然后问题就几乎解决了，因为最初保存了数字的异或版本，并且在需要时我们进行反转! 但这里的问题是找到集合中最大的数字(注意集合中的数字与原始数字不同)，所以命令3正确。我不知道如何在有效的时间内做到这一点。但我有一个想法:
如果我们首先将集合中数字的二进制表示形式保存在 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";
    }
}