1.题目大意：
a序列的n个数异或和为：a 1 a1a1 xor a 2 a2a2 xor a 3 a3a3 xor a 4 a4a4…xor a n anan
可以对一段连续的a l . . a r al..aral..ar加一，操作一次或者不操作，求操作之后的n个数的异或和
2.分析题目：
最后一定是前面一部分不加一，中间一部分加一，后面一部分不加一，注意每部分可能长度为0
维护两个前缀数组：
1.b [ i ] 维 护 前 i 个 a [ i ] + 1 的 异 或 和 b[i]维护前i个a[i]+1的异或和b[i]维护前i个a[i]+1的异或和
2.a [ i ] 维 护 前 i 个 a [ i ] 的 异 或 和 a[i]维护前i个a[i]的异或和a[i]维护前i个a[i]的异或和
3.再用字典树维护a[n] ^ a[i] ^ b[i]
为什么要字典树维护a[n]^a[i] ^b[i]呢？
想想，首先异或运算是满足交换律和结合律的
因为a [ i ] a[i]a[i]维护的是原a数组的前缀异或和，a[i]^a[n]剩下的是原a数组的，a[i+1] ^ a[i+2]…a[n]
b[i] ^ a[i] ^ a[n]为 原a数组的前i个(a[i]+1)异或和再异或原 数组的后面的n-i个a[i]的异或和
即 (a[1]+1) ^ (a[2]+1) ^(a[3]+1) ^ … ^(a[i]+1) ^a[i+1] ^a[i+2] ^… ^ a[n]
遍历一遍将所有的a[i]^a[n] ^b[i]放trie上面
4.再用a[i]^b[i]去查询trie上的最大异或对
为什么是a[i]^b[i]去查询呢？
因为答案一定是某一个 a[x] ^ b[x] ^ (a[n] ^ a[i] ^ b[i])
简单证明一下:
通过3已知，(a[n] ^ a[i] ^ b[i])为:
(a[1]+1) ^ (a[2]+1) ^(a[3]+1) ^ … ^(a[i]+1) ^a[i+1] ^a[i+2] ^… ^ a[n]
(这里的a数组是没有前缀处理的原a数组)
此时a[n] ^ a[i] ^ b[i]再异或b[x]^a[x]
就会将索引为1-x的异或变成0（(a[i]+1)^(a[i]+1)）,再将索引1-x的异或和变成a[1] ^ a[2] …a[x]
整个a[x] ^ b[x] ^ (a[n] ^ a[i] ^ b[i])变成:
a[1] ^ a[2] ^ …^ a[x] ^ (a[x+1]+1) ^ (a[x+1]+1) ^ (a[x+2]+1) …(a[x+k]+1) ^ a[x+k+1] ^ …a[n]
分成开始说的三段！
接下来就是求最大异或对了！
代码：
#include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) typedef pair<int, int> PII; #define ll long long #define endl "\n" #define LOCAL #define pb push_back const int N = 2e5 + 10, INF = 0x3f3f3f3f; inline int read() { int X = 0; bool flag = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') flag = 0; ch = getchar(); } while (ch >= '0' && ch <= '9') { X = (X << 1) + (X << 3) + ch - '0'; ch = getchar(); } if (flag) return X; return ~(X - 1); } inline void write(int X) { if (X < 0) { X = ~(X - 1); putchar('-'); } if (X > 9) write(X / 10); putchar(X % 10 + '0'); } int son[N][3]; int n; int idx, a[N], b[N]; void insert(int x) { int p = 0, u; for (int i = 31; i >= 0; i--) { u = (x >> i) & 1; if (!son[p][u]) son[p][u] = ++idx; p = son[p][u]; } } int query(int x) { int p = 0, u; int res = 0; for (int i = 31; i >= 0; i--) { u = (x >> i) & 1; if (son[p][u ^ 1]) res += 1 << i, p = son[p][u ^ 1]; else p = son[p][u]; } return res; } void solve() { n = read(); rep(i, 1, n) { a[i] = read(); b[i] = a[i] + 1; } for (int i = 1; i <= n; i++) { a[i] ^= a[i - 1]; b[i] ^= b[i - 1]; } for (int i = 0; i <= n; i++) { int x = a[n] ^ a[i] ^ b[i]; insert(x); } int ans = 0; for (int i = 0; i <= n; i++) ans = max(ans, query(b[i] ^ a[i])); cout << ans << "\n"; } int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int T = 1; //scanf("%d",&T); while (T--) { solve(); } return 0; }
撰文不易，点个赞再走吧！
