Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

02/21
10:17
可持久化数据结构 数据结构

BZOJ 3166 [Heoi2013]Alo 可持久化trie

Description

Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG , 如名字所见,到处充满了数学的谜题。 现在你拥有n颗宝石,每颗宝石有一个能量密度,记为ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设为 ai, ai+1, …, a j,则融合而成的宝石的能量密度为这些宝石中能量密度的次大值 与其他任意一颗宝石的能量密度按位异或的值,即,设该段宝石能量密度次大值 为k,则生成的宝石的能量密度为max{k xor ap | ap ≠ k , i ≤ p ≤ j}。 现在你需要知道你怎么选取需要融合的宝石,才能使生成的宝石能量密度最大。

Input

第一行,一个整数 n,表示宝石个数。 第二行, n个整数,分别表示a1至an,表示每颗宝石的能量密度,保证对于i ≠ j有 ai ≠ aj。

Output

输出一行一个整数,表示最大能生成的宝石能量密度。

Sample Input

5

9 2 1 4 7

Sample Output

14

HINT

【样例解释】

选择区间[1,5],最大值为 7 xor 9。

对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9

Source

加强型数据By Hta

Solution

窝真是太弱了……看了 黄学长的题解 才会做……

大体思路就是:

按照权值从大到小,把每个数的位置插入到set中去。

对于当前的数字x,在set中查询它的前驱的前驱,以及后继的后继,x的可行区间就为[前驱的前驱+1,x]和[x,后继的后继-1]。(为什么?这样的话,x在这两个区间内都是次大值)

然后就可以合并为一个区间啦,在可持久化trie中查询即可。