CodeForces 706D Vasiliy's Multiset 字典树

#include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<climits> #include<map> #include<bitset> using namespace std; const int maxn = 3*1e6+7; struct Tree { int Next[maxn][2]; int val[maxn]; int L,root; void init() { L=0; root = newnode(); } int newnode() { for(int i = 0; i<2; i++) Next[L][i]=-1; val[L++]=0; return L-1; } void Insert(int va) { int u = root,v; for(int i = 29; i>=0; i--) { v = (va&(1<<i))?1:0; if(Next[u][v]==-1) Next[u][v]=newnode(); u = Next[u][v]; val[u]++; } } void Delete(int va) { int u = root,v; for(int i = 29; i>=0; i--) { v = (va&(1<<i))?1:0; u = Next[u][v]; val[u]--; } } int Query(int x) { int u = root,v; for(int i = 29; i>=0; i--) { v = (x&(1<<i))?1:0; if(v==1) { if(Next[u][0]!=-1 && val[Next[u][0]]) u = Next[u][0]; else { u = Next[u][1]; x^=(1<<i); } } else { if(Next[u][1]!=-1 && val[Next[u][1]]) { u = Next[u][1]; x^=(1<<i); } else u = Next[u][0]; } } return x; } } ; int main() { Tree T; int q; T.init(); T.Insert(0); scanf("%d",&q); while(q--) { string op; int v; cin >> op >> v; if(op=="+") T.Insert(v); if(op=="-") T.Delete(v); if(op=="?") printf("%d\n",T.Query(v)); } return 0; }