[Codeforces] 842D. Vitya and Strange Lesson

題目連結:http://codeforces.com/problemset/problem/842/D

---

寫過類似的題目，一看到就認出來了XD。考慮把所有數字塞到bitwise的trie上，這樣xor一個數字時就變成交換左右子樹了，而且其實也不用真的把每個子樹都換過一遍，只要再走下去的時候看一下要誰當左右子樹即可。那這樣就只要在一棵樹上找mex值就好了，這也不難，只要維護一下每個子節點的大小，先看左子樹是不是空的，若是就直接回傳0，因為表示往左走都沒東東了，再看一下左子樹是不是滿的，若是就只能走右邊，不然就繼續走左子樹即可。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ALL(x) (x).begin(), (x).end()
const int N = 300000 + 5;
const int MEM = 20*N;

class Trie{
	private:
		struct node{
			node *l, *r;
			int size;
			node(){l=r=nullptr;size=0;}
		};
		node *root, pool[MEM];
		int _mem;
		node* newnode(){
			assert(_mem<MEM);
			pool[_mem]=node();
			return &pool[_mem++];
		}
		int size(node *x){return x?x->size:0;}
		void insert(int x, node *&cur, int d){
			if(!cur) cur=newnode();
			cur->size++;
			if(d>=32) return;
			if(x&1LL<<(31-d)) insert(x, cur->r, d+1);
			else insert(x, cur->l, d+1);
		}
		int find_min(node *cur, int d){
			if(cur->l) return find_min(cur->l, d+1);
			if(cur->r) return find_min(cur->r, d+1)+(1LL<<(31-d));
			return 0;
		}
		int mex(int xr, node *cur, int d){
			if(d>=32 or !cur) return 0;
			node *L=cur->l, *R=cur->r;
			if(xr & (1LL<<(31-d))) swap(L, R);
			if(size(L)>=(1LL<<(31-d))) return mex(xr, R, d+1)+(1LL<<(31-d));
			else return mex(xr, L, d+1);
		}
	public:
		void init(){_mem=0;root=nullptr;}
		void insert(int x){insert(x, root, 0);}
		int mex(int xr){return mex(xr, root ,0);}
		int find_min(){return find_min(root, 0);}
} tt;

vector<int> vv;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, q; cin>>n>>q;
	for(int i=0;i<n;i++){
		int x; cin>>x;
		vv.PB(x);
	}
	tt.init();
	sort(ALL(vv));
	vv.resize(distance(vv.begin(), unique(ALL(vv))));
	for(auto i: vv) tt.insert(i);
	int xr = 0;
	while(q--){
		int x; cin>>x;
		xr^=x;
		cout<<tt.mex(xr)<<'\n';
	}
	return 0;
}