【题意】点击打开链接
【解题方法】水题,字典树XOR搞一搞就好了。
【AC 代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e6+2;
struct node{
int ch[maxn][2];
int root,L;
int newnode(){
ch[L][0]=ch[L][1]=-1;
return L++;
}
void init(){
L=0;
root=newnode();
}
void Insert(int x){
int now=root;
for(int j=30; j>=0; j--){
int go=(x&(1<<j))?1:0;
if(ch[now][go]==-1){
ch[now][go]=newnode();
now=ch[now][go];
}else
now=ch[now][go];
}
}
int querymax(int x){
int now=root;
int ans=0;
for(int j=30; j>=0; j--){
int go=(x&(1<<j))?1:0;
if(ch[now][!go]!=-1){
ans|=(1<<j),now=ch[now][!go];
}else{
now=ch[now][go];
}
}
return ans;
}
int querymin(int x)
{
int now=root;
int ans=0;
for(int j=30; j>=0; j--){
int go=(x&(1<<j))?1:0;
if(ch[now][go]!=-1){
now=ch[now][go];
}else{
ans|=(1<<j);
now=ch[now][!go];
}
}
return ans;
}
}Trie;
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
char op[10];
int x;
Trie.init();
while(n--){
scanf("%s",op);
scanf("%d",&x);
if(strcmp(op,"insert")==0){
Trie.Insert(x);
}else if(strcmp(op,"qmin")==0){
printf("%d\n",Trie.querymin(x));
}else{
printf("%d\n",Trie.querymax(x));
}
}
}
}