一个线性空间复杂度的01Trie

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define L(i, l, r) for (int i = (l); i <= (r); i++)
#define R(i, r, l) for (int i = (r); i >= (l); i--)
#define wr(...) printf(__VA_ARGS__)

using sint = signed;

int rd() {
	int ret = 0;
	bool sgn = 0;
	char c = getchar();
	while (c < '0' || c > '9') {
		sgn |= (c == '-');
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return sgn ? -ret : ret;
}

constexpr int N = 1e5+7;
constexpr int inf = 0x3f3f3f3f3f3f3f3f;

namespace trie {
	constexpr int B=31;
	struct T {
		int v,h;
		sint ch[2];
	};
	T t[2*N];
	int ts;
	void init() {
		ts=0;
	}
	sint load(int v,int h) {
		assert(ts+1<2*N);
		t[++ts]= {v,h,{0,0}};
		return ts;
	}
	sint root() {
		return load(0,B);
	}
	int dif(int h,int x,int y) {
		R(i,h,0) {
			bool a=(x>>i)&1,b=(y>>i)&1;
			if(a!=b) {
				return i;
			}
		}
		return -1;
	}
	void insert(sint o,int x) {
		while(t[o].h>0) {
			bool b=(x>>(t[o].h-1))&1;
			int c=t[o].ch[b];
			if(c) {
				int d=dif(t[o].h,t[c].v,x);
				if(d>=t[c].h) {
					int a;
					t[o].ch[b]=a=load((x>>(d+1))<<(d+1),d+1);
					bool db=(x>>d)&1;
					t[a].ch[db]=load(x,0);
					t[a].ch[db^1]=c;
					o=t[a].ch[db];
				} else {
					o=c;
				}
			} else {
				t[o].ch[b]=load(x,0);
			}
		}
	}
	int query(sint o,int x) {
		while(t[o].h>0) {
			bool b=(x>>(t[o].h-1))&1;
			int c=t[o].ch[b^1];
			if(c) {
				o=c;
			} else {
				o=t[o].ch[b];
			}
		}
		return t[o].v;
	}
}

int n;
int a[N];
void task() {
	n=rd();
	int root=trie::root();
	L(i,1,n) {
		a[i]=rd();
		trie::insert(root,a[i]);
	}
	int ans=0;
	L(i,1,n) {
		int b=trie::query(root,a[i]);
		ans=max(ans,a[i]^b);
	}
	wr("%lld\n",ans);
}

sint main() {
	int T = 1;
	while (T--) {
		task();
	}
	return 0;
}