bdfz_2024_summer/day5/perfect/perfect.md

1.7 KiB
Raw Permalink Blame History

完美的答卷

题目背景

F 还是退役了,成为了超级银牌王。

也许多年以后他会忘掉排名,忘掉题目,忘掉 OI,甚至忘掉 A+B 怎么写。

但他永不会忘记那些热血沸腾、激动人心的瞬间。

这份 绝对的炽热,为他的 OI 生涯交出了完美的答卷。

题目描述

F 的生涯一共可以分成 n 个阶段,每个阶段有一个实力值 a_i , 保证实力值之间互不相同。

F 用一种奇怪的方式给他的每个生涯区间打了分。

对于 1 ≤ l ≤ r ≤ n,生涯区间 [l, r] 的分数 f (l, r) = \max\limits_{i=l}^{r} {a_i } ⊕ \min\limits_{i=l}^{r} {a_i } ,其中 表示按位异或。

F 想知道所有生涯区间的分数的最大值,也就是 $\max\limits_{1≤l≤r≤n} {f (l, r)}$。

这是他生涯中最后的愿望了。

输入格式

第一行一个正整数 n,表示阶段数量。

第二行 n 个非负整数,第 i 个整数 a_i 表示第 i 个阶段的实力值。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

5
2 1 5 3 4

样例输出 #1

7

提示

对于 100\% 的数据,$1 ≤ n ≤ 3 × 10^5 , 0 ≤ a_i ≤ 10^6$,保证 a_i 互不相同。

子任务 n≤ 特殊性质 得分
1 500 12
2 5000 16
3 3 × 10^5 A 8
4 3 × 10^5 B 16
5 3 × 10^5 C 20
6 3 × 10^5 28

特殊性质 A:保证对于所有 1 ≤ i < n,有 $a_i < a_{i+1}$。

特殊性质 B:保证对于所有 1 ≤ i < n,有 a_i \& a_{i+1} = 0,其中 \& 表示按位与。

特殊性质 C:保证数据随机。