D - 秋实大哥与快餐店

秋实大哥与快餐店

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

朝为田舍郎，暮登天子堂。秋实大哥从小就怀抱有远大的理想，所以他开了一家快餐店。

秋实大哥根据菜的口感，给每一道菜一个唯一的CIDCID，同时对于前来的客人，根据他们的口味喜好，秋实大哥会给每一个客人一个PIDPID。

对于一个标号为PIDPID的客人，他对标号为CIDCID的菜的喜爱程度为PID∧CIDPID∧CID(∧∧表示按位异或），该值越大表示越喜欢。

秋实大哥实在太忙了，现在他需要你来帮忙照看一下他的店铺。

Input

第一行包含一个整数nn，表示秋实大哥的餐馆内现在有nn道菜。

接下来一行包含nn个整数，分别表示每一道菜的CIDCID。

接下来一行包含一个整数mm，表示接下来发生了mm件事。

接下来的mm行，每一行为以下两种事件之一：

0 c : 表示秋实大哥最新研制出一道标号为c的菜

1 p : 表示来了一位标号为p的客人，请你在已有的菜中找出一道他最喜爱的菜

1≤n，m≤1000001≤n，m≤100000，0≤PID，CID≤10000000≤PID，CID≤1000000。

Output

对于每一个11 pp事件输出一个整数，表示该客人最喜欢的菜的标号。

Sample input and output

1 1 3 1 1 0 2 1 1

1 2

既然是求异或值，就把CID转换成二进制加入字典树，在把PID每一位取反转换成二进制在字典树里跑一遍就可以了

#pragma GCC diagnostic error "-std=c++11"

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

using namespace std;

struct Tire{

    struct Tire *next[];

    Tire() {next[] = next[] = NULL; }

};

Tire *root;

void Insert(int x){

    Tire *p = root;

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

        int c = (x >> i) & ;

        if(p -> next[c] == NULL)

            p -> next[c] = new Tire;

        p = p -> next[c];

    }

}

int Query(int x){

    x = ~x;

    Tire *p = root;

    int ans = ;

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

        int c = (x >> i) & ;

        ans <<= ;

        if( c ){

            if(p -> next[]){

                p = p -> next[];

                ans++;

            }else p = p -> next[];

        }else{

            if(p -> next[]) p = p -> next[];

            else{

                p = p -> next[];

                ans++;

            }

        }

    }

    return ans;

}

int main(){

    int n, x, m, c;

    root = new Tire;

    scanf("%d", &n);

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

        scanf("%d", &x);

        Insert( x );

    }

    scanf("%d", &m);

    for(int i = ; i <= m; i++){

        scanf("%d %d", &c, &x);

        if(c == ) Insert( x );

        else printf("%d\n", Query(x));

    }

}