題目來自DOTCPP：

思路：

什么是異或和？

①題目要求我們選擇兩個不相交的子段，我們可以枚舉一個分界線i，子段1在 i 的左邊， 子段2在 i 的右邊，分別找到子段1和子段2的最大值、最小值。

②怎么確定這兩個子段呢？根據： A^B=C --> A^C=B-->B^C=A 。

對于 i 左邊的子段，我們是從前往后枚舉的，因此可以先求出每個點的前綴異或和 ls[i]，ls[i]表示的是從0-i的子段的前綴異或和，我們在找到和 ls[i] 的最大異或和 ls[j]，ls[j]表示的是從0-j的前綴異或和，根據上面的原理，我們可以知道 0-i 這一段的最大異或和就是 i-j，我們可以把這個當前最大子段異或和存到 lmax[i]， 在和后面的比較。同理，如果我們要找的是和 ls[i] 異或的最小值 ls[k]，ls[k] 表示的是從 0-k 的前綴異或和，那么 0-i 這一段的最小異或和就是 k-i，將這一段的異或和存入?lmin[i]，和后面比較是否是最小值。

對于 i 右邊的子段，我們是從后往前枚舉的，因此可以求出每個點的后綴異或和 rs[i]，它表示 i-n 子段的后綴異或和。同樣的，我們找到 rs[i] 的最大異或和 rs[j]，那么 i-n 這個子段的最大異或和就是 i-j，將它存入到 rmax[i]。再找到 rs[i] 的最小異或和 rs[k]，i-n 這一段的最小異或和就是 i-k，將它存入到 rmin[i]。

③如何找到前綴異或和 ls[i] 的最小異或和、最大異或和？不能直接將所有數存入字典樹中，我們要存入的是前綴異或和，不能超過當前要找的這一段前綴異或和，然后在字典樹中查詢，我們要找的是最大值，就找和ls[i]相反的數。如果要找的是最小值，我們就要找和 ls[i] 相同的數字。

④最后，遍歷一下，有兩種情況：max（左邊子段最大值-右邊子段最小值，右邊子段最大值-左邊子段最小值）。

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+20;int n;
int arr[N];
int ls[N], rs[N]; //前綴異或和 后綴異或和
//第一個子段存到lch，第二個子段存到rch
//樹上存的是這個點的前綴異或和、后綴異或和
int idx, lch[N*31][2], rch[N*31][2];//節點編號 字典樹 
//最小值，最大值
int lmax[N], lmin[N], rmax[N], rmin[N];//將x插入到字典樹中
void add(int x, int ch[][2]){int p = 0;for(int i = 30; i >= 0; i--){int j = x>>i & 1;if(!ch[p][j]) ch[p][j] = ++idx;p = ch[p][j];}
}//查找和x異或最大值 在樹上找和他不相同的數
int queryMax(int x,int ch[][2]){int p = 0, res = 0;for(int i = 30; i >= 0; i--){int j = x >> i & 1;if(ch[p][!j]){res += 1 << i;p = ch[p][!j];}else p = ch[p][j];}return res;
}//查找和x異或最小值 在樹上要找和它相同的數
int queryMin(int x, int ch[][2]){int p = 0, res = 0;for(int i = 30; i >= 0; i--){int j = x>>i & 1;//如果有，異或后為0，不用加到res，反之，則要加上。if(ch[p][j]) p = ch[p][j];else{p = ch[p][!j];res += 1 << i;}}return res;
}signed main(){cin >> n;for(int i =1; i <= n; i++) cin >> arr[i];//初始化memset(lmin, N, sizeof lmin);memset(rmin, N, sizeof rmin);//找到左邊最大值、左邊最小值//樹上存的是這個點的前綴異或和add(0, lch);for(int i = 1; i <= n; i++){ls[i] = ls[i-1] ^ arr[i];lmax[i] = max(lmax[i-1], queryMax(ls[i], lch));lmin[i] = min(lmin[i-1], queryMin(ls[i], lch));//往樹上添加這個點前綴異或和add(ls[i], lch);}//找到右邊最大值add(0, rch);for(int i = n; i >= 1; i--){rs[i] = rs[i+1] ^ arr[i];rmax[i] = max(rmax[i+1], queryMax(rs[i], rch));rmin[i] = min(rmin[i+1], queryMin(rs[i], rch));add(rs[i], rch);}//枚舉分界線i 找到差值最大值int ans = 0;for(int i = 1; i < n; i++){//兩種情況 左邊最大值-右邊最小值//右邊最大值-左邊最小值ans = max(ans, max(lmax[i] - rmin[i], rmax[i] - lmin[i]));}cout << ans << endl;return 0;
}