2015 USTCデータ構造テーマC問題秋実兄貴とファーストフード店辞書ツリー

C-秋実兄貴とファーストフード店
Time Limit:1 Sec  メモリLimit:256 MB
タイトル接続http://acm.uestc.edu.cn/#/contest/show/59
Description
朝は田舎郎、暮れは天子堂.秋実さんは小さい時から大きな夢を抱いています.だから彼はファーストフード店を開業しました.
秋実さんは料理の味によって、一つの料理に一つのCIDをあげます.同時に来たお客さんに対して、好みによって、秋実さんはお客さんにPIDをあげます.
PIDという名前のお客さんにとって、CIDという名前の料理が好きなほどPIDΛCID(Λは位別または位別)で、この値が大きいほど好きです.
秋実さんはとても忙しいです.今彼はあなたに店の留守番をお願いします.
Input
1行目は整数nが含まれています.秋実さんのレストランには現在nコースの料理があります.次の行にはn個の整数が含まれています.それぞれの料理のCIDを表しています.次の行には整数mが含まれています.次のm行には下記の二つのイベントの一つがあります.0 c:秋実さんの最新の開発でcという料理の名前が出ています.pという名前のお客さんが来ました.既存の料理の中から彼の一番好きな料理を見つけてください.1≦n、m≦100000、0≦PID、CID≦100000.
Output
各1 pイベントに対して整数を出力し、そのお客様が一番好きな料理の番号を表します.
 
Sample Input
1
1
3
1
0 2
1
Sample Output
12
HINT
題意
クイズ:  辞書の木は、intの範囲なので、各数を2進にして、32位まで直接差し込むといいです.線分樹を走るたびに、反対方向に走るといいです.
コード:
 

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

class Trie
{
    public:
    Trie *next[2];
    Trie()
    {
        memset(next,NULL,sizeof(next));
    }
};

Trie *root;

void Insert(LL n)
{
    Trie *p = root;
    for(int i=31;i>=0;i--)
    {
        int id = (n >> i) & 1;
        if(p->next[id] == NULL)
             p->next[id] = new Trie();
        p = p->next[id];
    }
}

void Delete(Trie *T)
{
    if(T == NULL) return;
    for(int i=0;i<2;i++)
        if(T->next[i] != NULL)
            Delete(T->next[i]);
}

LL Match(LL m)
{
    m = ~m;
    LL ans = 0;
    Trie *p = root;
    for(int i=31;i>=0;i--)
    {
        ans <<= 1;
        int bit = (m >> i) & 1;
        if(bit)
        {
            if(p->next[1])
            {
                p = p->next[1];
                ans++;
            }
            else
            {
                p = p->next[0];
            }
        }
        else
        {
            if(p->next[0])
            {
                p = p->next[0];
            }
            else
            {
                p = p->next[1];
                ans++;
            }
        }
    }
    return ans;
}

int main()
{
    int n,m;
    root = new Trie();
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        LL val;
        scanf("%lld",&val);
        Insert(val);
    }
    scanf("%d",&m);
    while(m--)
    {
        int a;
        scanf("%d",&a);
        if(a==0)
        {
            LL val;
            scanf("%lld",&val);
            Insert(val);
        }
        else
        {
            LL val;
            scanf("%lld",&val);
            printf("%lld
",Match(val));
        }
    }
    return 0;
}