题目描述
原题来自:CODECHEF September Challenge 2015 REBXOR
给定一个含
N
N 个元素的数组
A
A,下标从
1
1 开始。请找出下面式子的最大值:
(A[l_1]\bigoplus A[l_1+1]\bigoplus …\bigoplus A[r_1])+ (A[l_2]\bigoplus A[l_2+1]^…\bigoplus A[r_2])
(A[l1
]⨁A[l1
+1]⨁…⨁A[r1
])+(A[l2
]⨁A[l2
+1]
…
⨁A[r2
]),其中
1\le l_1\le r_11≤l1
≤r1
≤r2
≤N,
x\bigoplus y
x⨁y 表示
x
x 和
y
y 的按位异或。
输入
输入数据的第一行包含一个整数
N
N,表示数组中的元素个数。
第二行包含
N
N 个整数
A[1],A[2],\ldots ,A[N]
A[1],A[2],…,A[N]。
输出
输出一行包含给定表达式可能的最大值。
样例输入
5
1 2 3 1 2
样例输出
6
提示
样例解释
满足条件的
(l_1,r_1,l_2,r_2)
(l1
,r1
,l2
,r2
) 有:
(1,2,3,3),(1,2,4,5),(3,3,4,5)
(1,2,3,3),(1,2,4,5),(3,3,4,5)。
数据范围与提示
对于
100\%
100% 的数据,
2\le N \le 4\times 10^5, 0\le A_i\le 10^9
2≤N≤4×105,0≤Ai
≤109。
来源/分类
ybttg 字典树 异或