题目链接：
http://codeforces.com/contest/706/problem/D
D. Vasiliy’s Multiset
time limit per test:4 secondsmemory limit per test:256 megabytes
#### 问题描述
> 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:
> 1. “+ x” — add integer x to multiset A.
> 2. “- 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.
> 3. “? 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.
输入
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.
输出
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.
样例
sample input
10
+ 8
+ 9
+ 11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11 sample output
11
10
14
13
题意
维护一个multiset，支持插入删除，并且对于查询“？ X”输出还在集合中的元素中与X最大的异或和。
题解
用trie树来维护集合，对于x，把它拆成32位二进制，然后按照从高位开始存到Trie里面，对于查询，只要在深搜Trie树的时候从高位开始故意往与x相反的方向跑就可以了。
代码
#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=(a);i<(b);i++)typedef __int64 LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;const int INF=1e9;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;//start----------------------------------------------------------------------const int maxnode=1e7+10;
const int maxm=34;int arr[66],tot;
int ch[maxnode][2];
int val[maxnode],tag[maxnode];
struct Trie{
int sz;
Trie(){
sz=1; clr(ch[0],0);
clr(val,0);
clr(tag,-1);
}
void insert(int x,int type){
int tmp=x;
int u=0, n=maxm;
tot=0;
clr(arr,0);
while(x){ arr[tot++]=x%2; x/=2; }
for(int i=n-1;i>=0;i--){
int c=arr[i];
val[u]+=type;
if(!ch[u][c]){
clr(ch[sz],0);
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]+=type;
tag[u]=tmp;
}
int query(int x){
int tmp=x;
int ret=0;
int u=0, n=maxm;
tot=0;
clr(arr,0);
while(x){ arr[tot++]=x%2; x/=2; }
int su=1;
for(int i=n-1;i>=0;i--){
int c=arr[i];
//printf("c:%d\n",c);
//printf("val[%d]:%d\n",u,val[u]);
if(ch[u][c^1]&&val[ch[u][c^1]]>0){
u=ch[u][c^1];
}else if(ch[u][c]&&val[ch[u][c]]>0){
u=ch[u][c];
}
else{
su=0;
break;
}
}
if(su) ret=max(tmp,tag[u]^tmp);
else ret=tmp;
return ret;
}
}trie;int main() {
int q;
scanf("%d",&q);
while(q--){
char cmd[11]; int x;
scanf("%s%d",cmd,&x);
if(cmd[0]=='+') trie.insert(x,1);
else if(cmd[0]=='-') trie.insert(x,-1);
else if(cmd[0]=='?') printf("%d\n",trie.query(x));
}
return 0;
}//end-----------------------------------------------------------------------
Notes
对于xor的操作，十有八九是要拆位考虑，拆完之后可以考虑用线段树，Trie树之类的数据结构去维护。
