这道题考察的是前缀和和trie树。
首先前缀异或和的性质还记得吧,s[l~r] = s[r]^s[l-1]
推导是这样的
s[l~r] = (a[1]^a[2]^…^a[l-1]^a[l]^…^a[r]) ^ (a[1]^a[2]^…^a[l-1])
= a[l]^a[l+1]^…^a[r]
我们要查询一段连续的区间的区间异或和,我们可以通过前缀异或和用O(1)的时间复杂度实现
同时,我们所查询的区间异或和还有性质,性质为区间和的最大值
因为是二进制数,我们很容易想到最大异或对那一题,所以,我们可以通过trie树来实现
我们先对已有的trie树进行相异查询,然后再往trie树中插入当前前缀异或和
想要让两个数s[l-1],s[r]的异或和最大,我们就可以每次查找s[r],在trie树中返回最大的trie的l-1
的下标
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 21 * N;
int n;
int s[N];
//id存的是每个数字的下标
int tr[M][2], id[M], idx;
void insert(int x, int k) {
int p = 0;
for (int i = 20; ~i; i -- ) {
int &s = tr[p][x >> i & 1];
if (!s) s = ++ idx;
p = s;
}
id[p] = k;
}
int query(int x) {
int p = 0;
for (int i = 20; ~i; i -- ) {
int u = x >> i & 1;
if (tr[p][!u]) p = tr[p][!u];
else p = tr[p][u];
}
return id[p];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &s[i]);
s[i] ^= s[i - 1];
}
int ans = -1;
int l, r;
for (int i = 1; i <= n; i ++ ) {
int k = query(s[i]);
int res = s[i] ^ s[k];
if (ans < res) ans = res, l = k + 1, r = i;
insert(s[i], i);
}
cout << ans << ' ' << l << ' ' << r << endl;
return 0;
}