OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HEOI2013】Alo

【题目描述】

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}。 

现在你需要知道你怎么选取需要融合的宝石,才能使生成的宝石能量密度最大。

【输入】

第一行,一个整数 n,表示宝石个数。 

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

【输出】

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

【输入样例】

5

9 2 1 4 7

【输出样例】

14

【数据范围】

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

【题解】

先处理次大值,我们先预处理出每个数能够成为次大值的区间,其实就是找到每个数左边和右边第二个大于它的数。我们用一棵平衡树来维护位置,将所有宝石按能量密度排序后插入即可。

接下来就是一个区间最大异或值的问题了,用可持久化Trie即可实现。

【代码】

一道set+可持久化Trie被我写成了Treap+可持久化Trie……

http://paste.ubuntu.com/11553161/

评论

© OI技术宅 | Powered by LOFTER