前缀和 + Tire + 贪心
时间复杂度:$O(nlog(n))$
先修课程:算法基础课 AcWing 835. Trie字符串统计、AcWing 143. 最大异或对、AcWing 795. 前缀和。
为什么 $s[i] \wedge s[j]$ 是为 $[i, j]$ 的异或和呢?
$s[i]$ 表示 $[1, i]$ 的异或和,$s[j]$ 表示 $[1, j]$ 的异或和,两者在 $[1, i]$ 在之间再进行异或则恰好为 $0$,结果就表示 $[i, j]$ 之间的异或和。
为什么能够保证所得到的异或和的长度最短呢?
当按照由小至大的顺序时,可保证末端整数的序列最小,遍历顺序也决定了覆盖机制。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5, M = 1e5 * 21;
int n;
int s[N], id[M], son[M][2], idx;
void insert(int x, int k)
{
int p = 0;
for (int i = 20; i >= 0; --i) {
int u = x >> i & 1;
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
id[p] = k;
}
int query(int x)
{
int p = 0;
for (int i = 20; i >= 0; --i) {
int u = x >> i & 1;
if (son[p][!u]) p = son[p][!u];
else p = son[p][u];
}
return id[p];
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
s[i] = s[i - 1] ^ x;
}
insert(s[0], 0);
int res = -1, a, b;
for (int i = 1; i <= n; ++i) {
int k = query(s[i]);
int t = s[i] ^ s[k];
if (res < t) {
res = t;
a = k + 1;
b = i;
}
insert(s[i], i);
}
cout << res << ' ' << a << ' ' << b << endl;
return 0;
}