字典树（Codeforces Round #367 (Div. 2)Vasiliy's Multiset，Xor问题 ）

1.题目链接：http://www.codeforces.com/problemset/problem/706/D

D. Vasiliy's Multiset time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard 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 x_i (1 ≤ x_i ≤ 10⁹). 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 x_i 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 .

 题意：有个多重集合，我们可以往里面加入一个数和删除一个数。也可以询问这个集合中的数与x异或的最最大值。

解法：对于求一个数对集合中的异或值最大，我们可以将集合中的树看成一个由其二进制组成的字符串。高位在前，低位在后。我们要求x与集合异或的最大值，我们只需在字典树中按位查找到与（~x）尽量相匹配的值（即高位尽可能的相等）。

AC：

#include<algorithm> #include<iostream> #include<cmath> #include<map> #include<string.h> #include<cstring> #include<vector> #include<queue> #include<stdio.h> using namespace std; #define ll long long int #define maxn 3000008 const int mod=20071027; int ch[maxn][2]; int val[maxn]; struct trie { public: int sz=1; void tt(){ sz=1; memset(ch[0],0,sizeof(ch[0]) ); };//初始化 void insert_(int v,int x)//插入，如果是删除的操作的话权值为-1 { int tp,u=0; for(int i=30;i>=0;i--) { tp=(x>>i)&1; if(!ch[u][tp]) { memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; ch[u][tp]=sz++; } u=ch[u][tp]; val[u]+=v; } }; int search_(int x)//查找到与~x尽量匹配的值 { int tp,u=0; int ans=0; for(int i=30;i>=0;i--) { tp=1-((x>>i)&1); if(!ch[u][tp])//如果不存在者位，则取另一位 { tp=1-tp; } else if(val[ch[u][tp]]<=0)//下一个的价值为0，不能取。只能取另一位 { tp=1-tp; } u=ch[u][tp]; // printf("%d:%d,",tp,val[u]); ans+=tp<<i; } //cout<<endl; return ans; } }t; int main(void) { //freopen("in.txt","r",stdin); int q,x; char s[10]; scanf("%d",&q); t.tt(); t.insert_(1,0); while(q--) { scanf("%s%d",&s,&x); if(s[0]=='+') t.insert_(1,x); else if(s[0]=='-') t.insert_(-1,x); else if(s[0]=='?') { printf("%d\n",x^t.search_(x)); } } } 题目2：链接： https://www.oj.swust.edu.cn/problem/show/2475 2475: Xor问题

Description

问题很简单，现在有一个数组a1，a2，a3……an。你的任务就是找到一个连续子段[l,r]，使得al^al+1^……^ar达到最大。

Input

多组输入，每组有两行。第一行有一个整数n(1<=n<=10^5)，表示数组的元素个数。第二行有n个元素，依次表示数组的元素。(0<=ai<=10^6)

Output

每组输出一行，这行仅一个数字。表示最大的连续子段异或值。

Sample InputRaw 5 1 2 3 4 5 5 2 3 2 3 2

Sample OutputRaw 7 3

解法：对于任意的L~R区间我们都可以用1->r区间的异或值异或上1->(l-1).所以我们可以将1-i( 0<i<=n)的异或值加入字典树，然后遍历找到其中最大的值既可以。

AC：

#include<algorithm> #include<iostream> #include<cmath> #include<map> #include<string.h> #include<cstring> #include<vector> #include<queue> #include<stdio.h> using namespace std; #define ll long long int #define maxn 1000008 const int mod=20071027; int ch[maxn][3]; int a[maxn]; struct trie { public: int sz=1; void tt(){ sz=1; memset(ch[0],0,sizeof(ch[0]) ); }; void insert_(int x) { int tp,u=0; for(int i=25;i>=0;i--) { tp=(x>>i)&1; if(!ch[u][tp]) { memset(ch[sz],0,sizeof(ch[sz])); ch[u][tp]=sz++; } u=ch[u][tp]; } }; int search_(int x) { int tp,u=0; int ans=0; for(int i=25;i>=0;i--) { tp=1-((x>>i)&1); if(!ch[u][tp]) { tp=1-tp; } u=ch[u][tp]; // printf("%d:%d,",tp,val[u]); ans+=tp<<i; } //cout<<endl; return x^ans; } }t; int main(void) { //freopen("in.txt","r",stdin); int n; a[0]=0; int k=0; while( scanf("%d",&n)!=EOF) { t.tt(); t.insert_(0); for( int j=1; j<=n; j++) { int d; scanf("%d",&a[j]); a[j]^=a[j-1]; t.insert_(a[j]); } int ans=0; for( int j=1;j<=n;j++) { ans=max(ans,t.search_(a[j])); } printf("%d\n",ans); } }