1
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
| #include <cstdio>
#define maxN 50010
struct Trie{ int son[2], sum, id; } a[maxN << 5];
int Ans = 0, cnt = 0;
int A[maxN];
int root[maxN], f[maxN];
int l1[maxN], l2[maxN], r1[maxN], r2[maxN];
int max (int x, int y)
{
return x > y ? x : y;
}
void build (int &now, int x, int w)
{
a[++cnt] = a[now];
now = cnt;
a[cnt].sum++;
if(w < 0)
{
a[cnt].id = x;
return ;
}
int p = (x >> w) & 1;
build(a[now].son[p], x, w - 1);
}
void work (int L, int R, int num, int x, int w)
{
if(w < 0)
{
Ans = max(Ans, num);
return ;
}
int p = !((x >> w) & 1);
if(a[a[R].son[p]].sum - a[a[L].son[p]].sum)
{
work(a[L].son[p], a[R].son[p], num + (1 << w), x, w - 1);
}
else
{
work(a[L].son[!p], a[R].son[!p], num, x, w - 1);
}
}
int main ()
{
int n = 0;
scanf("%d", &n);
for(int i = 1;i <= n; i++)
{
scanf("%d", &A[i]);
build(root[i] = root[i - 1], A[i], 30);
}
for(int i = 2;i <= n; i++)
{
l1[i] = i - 1;
while(l1[i] >= 1 && A[l1[i]] <= A[i])
{
l1[i] = l1[l1[i]];
}
l2[i] = l1[i] - 1;
while(l2[i] >= 1 && A[l2[i]] <= A[i])
{
l2[i] = l1[l2[i]];
}
}
r1[n] = n + 1;
for(int i = n - 1;i >= 1; i--)
{
r1[i] = i + 1;
while(r1[i] <= n && A[r1[i]] <= A[i])
{
r1[i] = r1[r1[i]];
}
r2[i] = r1[i] + 1;
while(r2[i] <= n && A[r2[i]] <= A[i])
{
r2[i] = r1[r2[i]];
}
}
for(int i = 1;i <= n; i++)
{
if(l1[i] >= 0 && r2[i] <= n + 1)
{
int L = l1[i] + 1;
int R = r2[i] - 1;
work(root[L - 1], root[R], 0, A[i], 30);
}
if(l2[i] >= 0 && r1[i] <= n + 1)
{
int L = l2[i] + 1;
int R = r1[i] - 1;
work(root[L - 1], root[R], 0, A[i], 30);
}
}
printf("%d", Ans);
return 0;
}
|