Nikitosh 和异或

class Solution_Case
{
	/*
	整体上比较有难度
	题意是找出左一端、右一段异或和，使他们的加和最大
	可以枚举中间的断点i，然后求 i的左边最大异或和+右边最大异或和 的max即可

	由此我们考虑如何维护出每一个位置i的左右最大异或和：
	问题有一个难点，trie树有可能前后不适用，所以要满足前面加入树的后面也可以用到
	而且我们的trie树只能做到选出两个数的异或和，仔细想想的话
	我们可以维护一个异或前缀和，并利用异或和的自反性
	设i<j，那么sum[1,i-1]^sum[1,j]就等于sum[i,j]

	综上所述，我们就可以想出一个线性思路：
	从左到右或者从右到左扫，同时维护一个从起点到当前指针的sum
	对于每个位置，将当前sum扔入树，查找当前sum可以配对的最大异或和，更新答案
	维护两遍以后，再按照最开始说的思路求左右两边max即可
	*/
};

#include<bits/stdc++.h>
#define N 400005
#define BetterIO \
	ios::sync_with_stdio(false);\
	cin.tie(0);\
	cout.tie(0)
using namespace std;

int trie[N * 33][2];	//2个子节点
int tot;
int n, a[N], L[N], R[N];

void Insert(int x)
{
	//插入树，根到叶子 为 数的左到右
	int p = 0;
	for (int i = 31; i >= 0; i--)
	{
		int u = (x >> i) & 1; //获取每个二进制位，依次为高位到低位
		if (!trie[p][u]) trie[p][u] = ++tot;
		p = trie[p][u];
	}
}

int Find(int x)
{
	//查找时候，尽量取不一样的数位，这样异或后的结果是1
	int p = 0, ans = 0;
	for (int i = 31; i >= 0; i--)
	{
		int u = (x >> i) & 1;
		if (trie[p][!u]) ans = ans * 2 + 1, p = trie[p][!u]; //反位有数，那么取反
		else ans *= 2, p = trie[p][u];	//反位无数，那么取本位
	}
	return ans;
}

signed main()
{
	BetterIO;
	cin >> n;
	Insert(0);
	for (int i = 1, sum = 0; i <= n; i++)	//从左向右
	{
		cin >> a[i];
		sum ^= a[i];
		Insert(sum);
		L[i] = max(L[i - 1], Find(sum));
	}
	tot = 0;
	memset(trie, 0, sizeof trie);
	Insert(0);
	for (int i = n, sum = 0; i > 0 ; i--)	//从右往左
	{
		sum ^= a[i];
		Insert(sum);
		R[i] = max(R[i + 1], Find(sum));
	}

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans = max({ans, L[i] + R[i + 1], L[i - 1] + R[i]});
	}
	cout << ans;
	return 0;
}