因为每个宝石只与另外一个宝石异或,可以发现宝石的左边比他大的第2个到右边比他大的第2个区间是这个宝石能够选取另一个与其异或的范围。
枚举每个宝石,找到左右区间,暴力更新即可。。。
标程是可持久化字典树。
mycode:
/**
* Problem:ALO
* Author:Shun Yao
* Time:2013.5.22
* Result:Accepted
*/
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
long max(long x, long y) {
return x > y ? x : y;
}
long n, l[50005], r[50005], a[50005], ans;
int main() {
static long i, j;
scanf("%ld", &n);
for (i = 1; i <= n; ++i)
scanf("%ld", a + i);
for (i = 1; i <= n; ++i) {
for (j = i - 1; j >= 1 && a[j] < a[i]; --j);
if (j >= 1) {
--j;
while (j >= 0 && a[j] < a[i])
--j;
l[i] = j + 1;
} else
l[i] = i + 1;
}
for (i = n; i >= 1; --i) {
for (j = i + 1; j <= n && a[j] < a[i]; ++j);
if (j <= n) {
++j;
while (j <= n && a[j] < a[i])
++j;
r[i] = j - 1;
} else
r[i] = i - 1;
}
ans = 0;
for (i = 1; i <= n; ++i)
for (j = l[i]; j <= r[i]; ++j)
ans = max(ans, a[i] ^ a[j]);
printf("%ld", ans);
return 0;
}