数组最大前缀后缀异或
描述
给一个长度为n的整数序列，现在要你截取这个序列的一个前缀和一个后缀(前缀和后缀不能相交)，使得前缀和后缀的异或值最大。
给一个长度为n的整数序列，现在要你截取这个序列的一个前缀和一个后缀(前缀和后缀不能相交)，使得前缀和后缀的异或值最大。
前缀和后缀可以为空，为空时他们的值为0。
input
有多组测试数据，请处理到文件结束。
对于每组测试数据，第一行包含一个整数n(1<=n<=100 000)。
接下来一行有n个用空格隔开的整数a1, a2, a3, …, an (0 <= ai <= 1000 000 000 000)。
output
对于每组测试数据输出一行，保包含一个整数，表示异或的最大的值。
sample input
2
1 2
3
1 2 3
2
1000 1000
sample output
3
3
1000
分析
因为两个相同的值异或为0，那么以 1 2 4 8 16 为例
如果 1 2 4 8为前缀， 4 8 16为后缀，他们是有交叉的，但由于异或的性质，他与 前缀1 2和后缀 16等价，因为中间相同的部分异或为0.
即 1^2^4^8^4^8^16 =1^2^16 。
这样我们先对所有前缀插入字典树，然后对于每一个后缀来查找，求出最大值即可。
即使交叉也无所谓，不会影响最后的结果，只是计算的复杂度有所增加。
注意这里的search函数里求result的方法
为了预防多次测试trie树没有清空造成错误，可以每次在while循环内部实例化root1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
long long num[N];
struct trie
{
trie* next[2];
trie()
{
next[0] = NULL;
next[1] = NULL;
}
};
trie* root;
void insert(long long num)
{
trie* p = root;
for (int i = 31; i>=0; i--)
{
int k = (num >> i) & 1;
if (p->next[k] == NULL)
{
p->next[k] = new trie();
}
p = p->next[k];
}
}
long long search(long long num)
{
long long result = 0;
num = ~num;
trie* p = root;
for (int i = 31; i >= 0; i--)
{
result<<=1;
int k = (num >> i) & 1;
if (k == 1)
{
if (p->next[1] != NULL)
{
result ++;
p = p->next[1];
}
else
{
p = p->next[0];
}
}
else
{
if (p->next[0] != NULL)
{
result ++;
p = p->next[0];
}
else
{
p = p->next[1];
}
}
}
return result;
}
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
root=new trie();
for (int i = 0; i<n; i++)
{
scanf("%lld", &num[i]);
}
long long temp=0;
insert(temp);
for (int i = 0; i<n; i++)
{
temp^=num[i];
insert(temp);
}
temp=0;
long long MAX=search(temp);
for(int j=n-1;j>=0;j--)
{
temp^=num[j];
long long cnt=search(temp);
if(cnt>MAX)
{
MAX=cnt;
}
}
printf("%lld\n", MAX);
}
return 0;
}