题目链接
B - 秋实大哥与快餐店
Time Limit:1000MS Memory Limit:65535KB 64bit IO Format:%lld & %llu
Appoint description:
System Crawler (2016-04-24)
System Crawler (2016-04-24)
Description
朝为田舍郎，暮登天子堂。秋实大哥从小就怀抱有远大的理想，所以他开了一家快餐店。
秋实大哥根据菜的口感，给每一道菜一个唯一的CID，同时对于前来的客人，根据他们的口味喜好，秋实大哥会给每一个客人一个
PID。
对于一个标号为PID的客人，他对标号为
CID的菜的喜爱程度为
PID∧CID(
∧表示按位异或），该值越大表示越喜欢。
秋实大哥实在太忙了，现在他需要你来帮忙照看一下他的店铺。
Input
第一行包含一个整数n，表示秋实大哥的餐馆内现在有
n道菜。
接下来一行包含n个整数，分别表示每一道菜的
CID。
接下来一行包含一个整数m，表示接下来发生了
m件事。
接下来的m行，每一行为以下两种事件之一：
0 c : 表示秋实大哥最新研制出一道标号为c的菜
1 p : 表示来了一位标号为p的客人，请你在已有的菜中找出一道他最喜爱的菜
，
1≤n，m≤100000，
，
0≤PID，CID≤1000000。
Output
对于每一个1
p事件输出一个整数，表示该客人最喜欢的菜的标号。
Sample Input
1
1
3
1 1
0 2
1 1
Sample Output
1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
const double pi=acos(-);
const int maxn=;
struct data{
int l,r,id,flag;
}tree[(<<)+]; void insertc(int x)
{
int ptr=;
for(int i=;i>=;i--)
{
if(x&(<<i))
{
tree[ptr].r=;
ptr=*ptr+;
}
else
{
tree[ptr].l=;
ptr=*ptr;
}
}
tree[ptr].id=x;
}
//在字典树中插入字符
int findc(int x)
{
int ptr=;
for(int i=;i>=;i--)
{
if(x&(<<i))
{
if(tree[ptr].l)
ptr=*ptr;
else ptr=*ptr+;
}
else
{
if(tree[ptr].r)
ptr=*ptr+;
else ptr=*ptr;
}
}
return tree[ptr].id;
}
//查找字符
int main()
{
int n,m;
while(~scanf("%d",&n))
{
MM(tree,);
int x,y;
for(int i=;i<=n;i++)
{
scanf("%d",&x);
insertc(x);
} scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d %d",&x,&y);
if(!x) insertc(y);
else printf("%d\n",findc(y));
}
}
return ;
}
分析：字典树处理，注意开的数组的大小，是将1e6用trie树存储，转化成二进制2^20>=1e6，
比如（2^20）1000...(20个0)，