题目
有q次操作，每次操作是以下两种：
1、 加入一个数到集合中
2、 查询，查询当前数字与集合中的数字的最大异或值，最大and值，最大or值
输入
第一行1个正整数Q表示操作次数
接下来Q行，每行2个数字，第一个数字是操作序号OP（1,2），第二个数字是X表示操作的数字
输出
输出查询次数行，每行3个整数，空格隔开，分别表示最大异或值，最大and值，最大or值
样例输入
【输入样例1】
5
1 2
1 3
2 4
1 5
2 7
【输出样例1】
7 0 7
5 5 7
【样例解释1】
询问4时，已插入2、3，最大异或值为4^3=7，最大and值为4&3或4&2=0，最大or值为4|3=7
询问7时，已插入2、3、5，最大异或值为7^2=5，最大and值为7&5=5，最大or值为7|2=7|3=7|5=7
【输入样例2】
10
1 194570
1 202332
1 802413
2 234800
1 1011194
2 1021030
2 715144
2 720841
1 7684
2 85165
【输出样例2】
1026909 201744 1032061
879724 984162 1048062
655316 682376 1043962
649621 683464 1048571
926039 85160 1011199
样例输出 [复制]
提示
对于%10的数据1<=Q<=5000
对于另%10的数据保证 X<1024
对于另%40的数据保证1<=Q<=100000
对于所有数据保证1<=Q<=1000000,1<=X<=2^20 保证第一个操作为1操作。
异或操作很简单，建trie树就是了，而&和 | 可以按位贪心
比如&时，如果x该位已为0，那么0和1都是可以的，于是只需要给子集打标记，默认填0
|也是基本上一样的
代码
#include<bits/stdc++.h>
using namespace std;
int q,trans[(1<<21)+3][2],tot=1,op,x;
inline int read(){
char ch;
while((ch=getchar())<'0'||ch>'9'){;}
int res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return res;
}
int le[1<<20];
inline void mark(int x)
{
le[x]=1;
for(int i=0;i<20;i++)
{
if((x>>i&1)&&(!le[x^(1<<i)])) mark(x^(1<<i));
}
}
inline void insert(int k)
{
int p=1;
for(int i=19;~i;i--)
{
int c=(k>>i&1?1:0);
if(!trans[p][c]) trans[p][c]=++tot;
p=trans[p][c];
}
}
inline int find(int k)
{
int p=1,now=0;
for(int i=19;~i;i--)
{
int c=(k>>i&1?0:1);
if(trans[p][c])
{
p=trans[p][c];
if(c)
now|=1<<i;
}
else
{
p=trans[p][c^1];
if(c^1) now|=1<<i;
}
}
return now;
}
int main(){
q=read();
for(int o=1;o<=q;o++)
{
op=read(),x=read();
if(op==1)
{
mark(x);
insert(x);
}
else
{
printf("%d ",find(x)^x);
int now=0;
for(int i=19;~i;i--)
{
if((x>>i&1)&&le[now|1<<i]) now|=1<<i;
}
printf("%d ",now&x);
now=0;
for(int i=19;~i;i--)
{
if((!(x&(1<<i)))&&le[now|1<<i]) now|=1<<i;
}
printf("%d
",now|x);
}
}
}