Vitya and Strange Lesson

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
int tr[maxn * 32][2];
bool full[maxn * 32];
int n, m, cnt;
void add(int x){
    int cur = 0;
    for(int i = 30; i >= 0; i--){
        int f = (x >> i) & 1;
        if(!tr[cur][f]) tr[cur][f] = ++cnt;
        cur = tr[cur][f];
    }
}
void dfs(int u){
    bool f = true;
    int lson, rson;
    lson = tr[u][0]; rson = tr[u][1];
    if(!lson && !rson){
        full[u] = true;
        return ;
    }//叶子节点
    if(lson){
        dfs(lson);
        if(!full[lson]) f = false;
    }
    else f = false;
    if(rson){
        dfs(rson);
        if(!full[rson]) f = false;
    }
    else f = false;
    full[u] = f;
}
int query(int x){
    int cur = 0; int ans = 0;
    for(int i = 30; i >= 0; i--){
        int f = (x >> i) & 1;
        if(!tr[cur][f]){
            break;
        }
        if(!full[tr[cur][f]]) cur = tr[cur][f];
        else{
            f ^= 1;
            ans += 1 << i;
            //printf("i = %d\n", i);
            if(!tr[cur][f]) break;
            cur = tr[cur][f];
        }
    }
    return ans;
}
void print(){
    for(int i = 0; i <= cnt; i++){
        cout << "i = " << i << endl;
        cout << "lson = " << tr[i][0] << " rson = " << tr[i][1] << endl;
        cout << "full = " << full[i] << endl;
    }
}
int main(){
    scanf("%d%d", &n, &m);
    int x, p;
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        add(x);
    }
    dfs(0);
    //print();
    x = 0;
    for(int i = 1; i <= m; i++){
        scanf("%d", &p);
        x ^= p;
        printf("%d\n", query(x));
    }
    return 0;
}