【bzoj3166】[Heoi2013]Alo

2014年12月18日3,2142

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

题解

按照权值的倒序,set维护位置,依次插入,则x的可行区间为[x前驱的前驱+1,x后继的后继-1](两半合起来)

用可持久化trie支持查询区间xor最大值

 

  • 罗崚骁2016年2月24日 下午1:25 回复

    滴滴滴QWQ我觉得可以不用set倒着插入,正着用双向链表不断删除就可以惹owo

    #1