D. Vitya and Strange Lesson time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Today at the lesson Vitya learned a very interesting function — mex. Mex of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example, mex([4, 33, 0, 1, 1, 5]) = 2 and mex([1, 2, 3]) = 0.
Vitya quickly understood all tasks of the teacher, but can you do the same?
You are given an array consisting of n non-negative integers, and m queries. Each query is characterized by one number x and consists of the following consecutive steps:
Perform the bitwise addition operation modulo 2 (xor) of each array element with the number x. Find mex of the resulting array. Note that after each query the array changes.
Input First line contains two integer numbers n and m (1 ≤ n, m ≤ 3·105) — number of elements in array and number of queries.
Next line contains n integer numbers ai (0 ≤ ai ≤ 3·105) — elements of then array.
Each of next m lines contains query — one integer number x (0 ≤ x ≤ 3·105).
Output For each query print the answer on a separate line.
Examples input 2 2 1 3 1 3 output 1 0 input 4 3 0 1 5 6 1 2 4 output 2 0 0 input 5 4 0 1 5 6 7 1 1 4 5 output 2 2 0 2
题意：n个数，m个询问，问异或后不存在的最小的数
逆向思维 每一个数异异或一个数的值都是不一样的，第一种想法是把不存在的数加到字典树上，然后找异或到的最小值,得开 21*（1<<20)的内存有点多了。。
#include <bits/stdc++.h> using namespace std; const int N = (1<<20); const int BB=22; struct node { int nxt[2]; }T[N*BB+1]; int mp[(1<<20)]; typedef long long ll; int sz; void insert(int d) { int p=0; for(int i=21;i>=0;i--) { int dd=(d>>i)&1; if(!T[p].nxt[dd]) T[p].nxt[dd]=++sz; p=T[p].nxt[dd]; } } int go[32]; int ans; void ask() { int p=0; for(int i=21;i>=0;i--) { int dd=go[i]; if(T[p].nxt[dd]) p=T[p].nxt[dd]; else { p=T[p].nxt[1-dd],ans|=(1<<i); } } } int main(){ memset(T,0,sizeof(T)); int n,m; scanf("%d%d",&n,&m); sz=0; for(int i=1;i<=n;i++) { int d; scanf("%d",&d); mp[d]=1; } for(int i=0;i<=(1<<20);i++) { if(!mp[i]) insert(i); } int t=0; while(m--){ int x; scanf("%d",&x); t^=x; ans=0; for(int j=21;j>=0;j--) { int dd=(t>>j)&1; go[j]=dd; } ask(); printf("%d\n",ans); } }第二种方法是判断子树是不是满的 往不满的子树走，异或同方向的优先 重复的点要删除
#include <bits/stdc++.h> using namespace std; const int N = 300010; const int BB=22; struct node { int nxt[2]; }T[N*BB+1]; int size[N*BB+1]; typedef long long ll; int sz; int go[32]; int ask() { int p=0,ans=0; for(int i=21;i>=0;i--) { int dd=go[i]; if(!T[p].nxt[dd]) return ans; if(size[T[p].nxt[dd]]<(1<<i)) p=T[p].nxt[dd]; else { ans|=(1<<i); p=T[p].nxt[1-dd]; if(!p) return ans; } } return ans; } void insert(int d) { int p=0; for(int i=21;i>=0;i--) { int dd=(d>>i)&1; if(!T[p].nxt[dd]) T[p].nxt[dd]=++sz; p=T[p].nxt[dd]; size[p]++; } if(size[p]>1) { p=0; for(int i=21;i>=0;i--) { int dd=(d>>i)&1; p=T[p].nxt[dd]; size[p]--; } } } int main(){ memset(T,0,sizeof(T)); memset(size,0,sizeof(size)); int n,m; scanf("%d%d",&n,&m); sz=0; for(int i=1;i<=n;i++) { int d; scanf("%d",&d); insert(d); } int tt=0; while(m--){ int x; scanf("%d",&x); tt^=x; for(int j=21;j>=0;j--) { int dd=(tt>>j)&1; go[j]=dd; } printf("%d\n",ask()); } }