问题 I: [Heoi2013]Alo
时间限制: 3 Sec 内存限制: 256 MB
提交: 64 解决: 24
[提交][状态][讨论版]
题目描述
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
提示
【样例解释】
选择区间[1,5]，最大值为 7 xor 9。
对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9
可持久化01Trie正式入坑。。其实和主席树整体上是一样的，但这里就区别于普通Trie树了。普通的是在不同的地方建一条新枝。可持久的依然是完全新建一条链。
这道题利用的区间异或的最大值，就是在这个区间一位位贪心地向下找。做减法判断区间里是否有能对答案产生贡献的元素，有就选就选，并向相应的子节点推进。
这道题其他的地方：次大值。。考虑把权值排序后从大到小插入一个set。所以当前set里所有位置对应的值都是比当前元素大的。那么他是次大的区间就是前驱的前驱位置+1,后继的后继的位置-1.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#define N 50005
#define inf 1000000000
using namespace std;
int n,ans,xp[31];
struct node{
int h,id;}a[N];
set<int> st;
namespace TRIE
{struct trie{trie* ch[2];int sum;trie(){sum=0;ch[0]=ch[1]=NULL;}}*null=new trie(),*root[N];trie* newtrie(){trie* o=new trie();o->ch[0]=o->ch[1]=null;return o;}void ins(trie* &now,trie* pre,int x,int i){if(i<0)return;int k=x&xp[i];k>>=i;now->ch[k^1]=pre->ch[k^1];now->ch[k]=newtrie();now->ch[k]->sum=pre->ch[k]->sum+1;ins(now->ch[k],pre->ch[k],x,i-1);}int q(trie* l,trie* r,int x){int tmp=0;for(int i=30;i>=0;i--){int k=x&xp[i];k>>=i;if(r->ch[k^1]->sum-l->ch[k^1]->sum)l=l->ch[k^1],r=r->ch[k^1],tmp+=xp[i];else l=l->ch[k],r=r->ch[k];}return tmp;}
}
using namespace TRIE;
inline bool cmp(node a,node b){
return a.h>b.h;}
int main()
{scanf("%d",&n);null->ch[0]=null->ch[1]=null;xp[0]=1;for(int i=1;i<=30;i++)xp[i]=xp[i-1]<<1;for(int i=1;i<=n;i++)scanf("%d",&a[i].h),a[i].id=i;for(int i=0;i<=n;i++)root[i]=newtrie();for(int i=1;i<=n;i++)ins(root[i],root[i-1],a[i].h,30);sort(a+1,a+n+1,cmp);st.insert(-1);st.insert(0);st.insert(n+1);st.insert(n+2);st.insert(a[1].id);set<int>::iterator it1,it2; for(int i=2,l,r;i<=n;i++){st.insert(a[i].id);it1=it2=st.find(a[i].id);it1--;it1--;l=*it1+1;l=max(l,1);it2++;it2++;r=*it2-1;r=min(n,r);if(l!=r)ans=max(ans,q(root[l-1],root[r],a[i].h));}printf("%d\n",ans);
}