题意：进行n次操作0在集合内
+表示将x加入集合内
- 表示将x删除集合内
？表示查询x与集合内的数的异或的最大值
思路：xor数---存起来当模板
ACcode：
#include<iostream> #include<cstdio> using namespace std; #define maxn 500000 * 2 * 20 int ch[maxn][2]; int cnt[maxn]; int clk = 1; void insert(int x) { int root = 1; cnt[root]++; for (int i = 30; i >= 0; i--) { int s; if (x & (1 << i)) s = 1; else s = 0; if (!ch[root][s]) ch[root][s] = ++clk; root = ch[root][s]; cnt[root]++; } } void remove(int x) { int root = 1; cnt[root]--; for (int i = 30; i >= 0; i--) { int s; if (x & (1 << i)) s = 1; else s = 0; root = ch[root][s]; cnt[root]--; } } int query(int x) { int rt = 1; int ret = 0; for (int i = 30; i >= 0; i--) { int s; if (x & (1 << i)) s = 1; else s = 0; if (cnt[ch[rt][!s]]) { ret |= 1 << i; rt = ch[rt][!s]; } else rt = ch[rt][s]; } return ret; } int main() { int n; scanf("%d", &n); insert(0); while (n--) { char s[10]; scanf("%s", s); int x; scanf("%d", &x); if (s[0] == '+') insert(x); else if (s[0] == '-') remove(x); else printf("%d\n", query(x)); } return 0; }
