蓝桥杯2023年第十四届省赛真题-异或和之差

题目来自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;
}