ACdream 1063 字典树

                                          平衡树

神奇的cxlove有一颗平衡树，其树之神奇无法用语言来描述 OrzOrz。 这棵树支持3种操作： 1、加入一个数到树中，维护平衡树的合法性； 2、给一个数X，用O(1)的时间求出来树中的数Y使得 Y ^ X 最大（异或操作， Pascal 写作 xor , 0 ^ 0 = 0 , 1 ^ 1 = 0 , 0 ^ 1 = 1 , 1 ^ 0 = 1 , 2 ^ 3 = 1） 3、给一个数X，用O(1)的时间求出来树中的数Y使得 Y ^ X 最小（异或操作， Pascal 写作 xor , 0 ^ 0 = 0 , 1 ^ 1 = 0 , 0 ^ 1 = 1 , 1 ^ 0 = 1 , 2 ^ 3 = 1） 请你帮忙实现这颗树。 cxlove由于过于牛，有些事情是无法做到的，你能在1s以内通过就好了。 最后补充一句，cxlove是世界冠军！

Input

第一行是数据组数T (T ≤ 100)。

对于每组数据，第一行是操作数N (N ≤ 10000)。

以下 N 行，每行一个字符串一个数字，分别代表：

insert X ，加入数 X

qmax X ，求第2种操作的答案

qmin X ，求第3种操作的答案

输入保证不存在空树Query的情况 (1 ≤ X ≤ 1e9)

Output

对于操作 2 , 3 输出相应的答案。

Sample Input

1

4

insert 1

insert 2

qmin 1

qmax 1

Sample Output

0

3

Hint

Huge input and output. Please do not use: 1. cin ans cout of C++ 2. scanner of Java(Maybe BufferedReader is quicker)

Source

buaads

Manager

传送门

题目名相当不厚道，很显然求xor最大最小值使用01 tree才对。

01字典树，同字典树，只是将数字当做01串进行处理，那么对于一个数，求最大xor就往方向走，求最小xor就往同方向走就好

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

const int N=320000;

const int sigma=2;

int ch[N][sigma];

int var[N],sz;

void clear(){

    sz=1;

    memset(ch[0],0,sizeof(ch[0]));

}

void insert(int x){

    int u=0;

    for(int i=31;i>=0;i--){

        int c=(x>>i)&1;

        if(!ch[u][c]){

            memset(ch[sz],0,sizeof(ch[sz]));

            ch[u][c]=sz;

            var[sz++]=0;

        }

        u=ch[u][c];

    }

    var[u]=x;

}

int search(int x){

    int u=0;

    for(int i=31;i>=0;i--){

        int c=(x>>i)&1;

        if(ch[u][c^1]) u=ch[u][c^1];

        else u=ch[u][c];

    }

    return var[u];

}

int search2(int x){

    int u=0;

    for(int i=31;i>=0;i--){

        int c=(x>>i)&1;

        if(ch[u][c]) u=ch[u][c];

        else u=ch[u][c^1];

    }

    return var[u];

}

int main(){

    int T=read();

    while(T--)

    {

        int n;

        n=read();

        clear();

        char op[30];

        int x;

        ll tmp;

        for(int i=0; i<n; i++)

        {

            scanf("%s",op);x=read();

            if(strcmp(op,"insert")==0) insert(x);

            else if(strcmp(op,"qmax")==0)

            {

                tmp=search(x);

                printf("%lld\n",tmp^x);

            }

            else

            {

                tmp=search2(x);

                printf("%lld\n",tmp^x);

            }

        }

    }

    return 0;

}