链接：戳这里
D. Vasiliy's Multiset time limit per test4 seconds memory limit per test256 megabytes inputstandard input outputstandard output Author has gone out of the stories about Vasiliy, so here is just a formal task description. You are given q queries and a multiset A, initially containing only integer 0. There are three types of queries: "+ x" — add integer x to multiset A. "- x" — erase one occurrence of integer x from multiset A. It's guaranteed that at least one x is present in the multiset A before this query. "? x" — you are given integer x and need to compute the value , i.e. the maximum value of bitwise exclusive OR (also know as XOR) of integer x and some integer y from the multiset A. Multiset is a set, where equal elements are allowed. Input The first line of the input contains a single integer q (1 ≤ q ≤ 200 000) — the number of queries Vasiliy has to perform. Each of the following q lines of the input contains one of three characters '+', '-' or '?' and an integer xi (1 ≤ xi ≤ 109). It's guaranteed that there is at least one query of the third type. Note, that the integer 0 will always be present in the set A. Output For each query of the type '?' print one integer — the maximum value of bitwise exclusive OR (XOR) of integer xi and some integer from the multiset A. Example input 10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11 output 11 10 14 13 Note After first five operations multiset A contains integers 0, 8, 9, 11, 6 and 1. The answer for the sixth query is integer — maximum among integers , , , and . 题意：
n 个操作
+ x 表示向集合添加一个数x
- x 表示集合里面减少一个数x
？x 找出集合里面一个数y使得x^y最大
思路：
裸的trie树，注意先插个0进去
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<vector> #include <ctime> #include<queue> #include<set> #include<map> #include<list> #include<stack> #include<iomanip> #include<cmath> #include<bitset> #define mst(ss,b) memset((ss),(b),sizeof(ss)) ///#pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; #define INF (1ll<<60)-1 #define Max 80*100000 using namespace std; int num[Max],cnt=1; int d[Max][2]; void update(int x){ int p=1; for(int i=30;i>=0;i--){ if(d[p][(x>>i)&1]==0) d[p][(x>>i)&1]=++cnt; p=d[p][(x>>i)&1]; num[p]++; } } void update1(int x){ int p=1; for(int i=30;i>=0;i--){ p=d[p][(x>>i)&1]; num[p]--; } } int query(int x){ int ans=0; int p=1; for(int i=30;i>=0;i--){ int t=(x>>i)&1; if(num[d[p][1^t]]) p=d[p][1^t],ans+=(1<<i); else p=d[p][t]; } return ans; } char s[10]; int x; int main(){ int n; scanf("%d",&n); update(0); for(int i=1;i<=n;i++){ scanf("%s%d",s,&x); if(s[0]=='+'){ update(x); } else if(s[0]=='-'){ update1(x); } else { printf("%d\n",query(x)); } } return 0; }
