1777F - Comfortably Numb - CodeForces Solution

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
 
const int K = 30;
const int N = 200200;
const int M = N * (K + 1) + 7;
int n, m;
int ANS;
int a[N];
int pref[N];
pii segm[N];
int st[N];
int sz;
int par[N];
vector<int> g[N];
int to[M][2];
 
int getNewNode() {
	to[m][0] = to[m][1] = -1;
	return m++;
}
int createTrie(int x) {
	int v = getNewNode();
	int r = v;
	for (int k = K - 1; k >= 0; k--) {
		int u = getNewNode();
		to[v][(x >> k) & 1] = u;
		v = u;
	}
	return r;
}
int findBiggestXor(int v, int x) {
	assert(v != -1);
	int res = 0;
	for (int k = K - 1; k >= 0; k--) {
		int c = (x >> k) & 1;
		if (to[v][c ^ 1] != -1) {
			res ^= 1 << k;
			v = to[v][c ^ 1];
		} else {
			v = to[v][c];
			assert(v != -1);
		}
	}
	return res;
}
int mergeTries(int v, int u) {
	if (v == -1) return u;
	if (u == -1) return v;
	for (int c = 0; c < 2; c++)
		to[v][c] = mergeTries(to[v][c], to[u][c]);
	return v;
}
 
int solve(int v) {
	int l = segm[v].first, r = segm[v].second;
	eprintf("solve %d (%d %d)\n", v, l, r);
	int rootL = -1, rootR = -1;
	for (int u : g[v]) {
		int cur = solve(u);
		if (u < v) {
			assert(rootL == -1);
			rootL = cur;
		} else {
			assert(rootR == -1);
			rootR = cur;
		}
	}
	if (rootL == -1) {
		assert(v - l == 1);
		rootL = createTrie(pref[v]);
	}
	if (rootR == -1) {
		assert(r - v == 1);
		rootR = createTrie(pref[v + 1]);
	}
	if (v - l < r - v) {
		for (int i = l + 1; i <= v; i++) {
			ANS = max(ANS, findBiggestXor(rootR, pref[i] ^ a[v]));
		}
		return mergeTries(rootR, rootL);
	} else {
		for (int i = v + 1; i <= r; i++) {
			ANS = max(ANS, findBiggestXor(rootL, pref[i] ^ a[v]));
		}
		return mergeTries(rootL, rootR);
	}
}
 
void solve() {
	scanf("%d", &n);
	pref[0] = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		pref[i + 1] = pref[i] ^ a[i];
	}
	ANS = 0;
	sz = 0;
	st[0] = -1;
	for (int i = 0; i < n; i++) {
		while(sz > 0 && a[i] > a[st[sz]]) sz--;
		segm[i].first = st[sz];
		st[++sz] = i;
	}
	sz = 0;
	st[0] = n;
	for (int i = n - 1; i >= 0; i--) {
		while(sz > 0 && a[i] >= a[st[sz]]) sz--;
		segm[i].second = st[sz];
		st[++sz] = i;
	}
	for (int i = 0; i < n; i++)
		eprintf("%d %d\n", segm[i].first, segm[i].second);
	for (int i = 0; i < n; i++)
		g[i].clear();
	int root = -1;
	for (int i = 0; i < n; i++) {
		if (segm[i] == mp(-1, n)) {
			par[i] = -1;
			root = i;
			continue;
		}
		if (segm[i].first == -1) {
			par[i] = segm[i].second;
		} else if (segm[i].second == n) {
			par[i] = segm[i].first;
		} else {
			int v = segm[i].first, u = segm[i].second;
			if (segm[v].second - segm[v].first < segm[u].second - segm[u].first)
				par[i] = v;
			else
				par[i] = u;
		}
		g[par[i]].push_back(i);
	}
	for (int i = 0; i < n; i++)
		eprintf("par[%d] = %d\n", i, par[i]);
	m = 0;
	solve(root);
	printf("%d\n", ANS);
}
 
int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	int t;
	scanf("%d", &t);
	while(t--) solve();
 
	return 0;
}