1618: Nikitosh 和异或

题目描述


原题来自: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 字典树 异或

请先 登录 后评论
  • 0 关注
  • 0 收藏,661 浏览
  • 轩爸 提出于 2019-08-02 22:15

相似问题