bzoj 3166 [Heoi2013]Alo

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

题解

区间xor最大，就是可持久化Trie往上套。

区间次大，set随便维护一下。

#include <cstdio>
#include <set>
#include <algorithm>
#include <cstring>
#define N 50010
#define inf 0x3f3f3f3f
using namespace std;
set<int>se;
struct data{int v,id;}a[N];
bool comp(data a,data b){return a.v>b.v;}
int val[N*40],ch[N*40][2],sz,root[N*40],n,ans;
void insert(int &now,int x,int dep)
{
    val[++sz]=val[now]+1,ch[sz][0]=ch[now][0],
    ch[sz][1]=ch[now][1],now=sz;
    if (dep==-1) return;
    insert(ch[now][1&(x>>dep)],x,dep-1);
}
int query(int l,int r,int x,int dep)
{
    if (dep==-1) return 0;
    if (val[ch[r][(1&(x>>dep))^1]]-val[ch[l][(1&(x>>dep))^1]]>0)
        return (query(ch[l][(1&(x>>dep))^1],ch[r][(1&(x>>dep))^1],x,dep-1)|(1<<dep));
    else
        return query(ch[l][1&(x>>dep)],ch[r][1&(x>>dep)],x,dep-1);
}
main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i].v),a[i].id=i;
    for (int i=1;i<=n;i++)
        root[i]=root[i-1],insert(root[i],a[i].v,31);
    sort(a+1,a+1+n,comp);
    se.insert(-1);se.insert(inf);se.insert(-2);se.insert(inf+1);
    se.insert(a[1].id);
    for(int i=2;i<=n;i++)
    {
        int l=a[i].id,r=a[i].id,x=a[i].id;
        set<int>::iterator s1,s2;
        s1=s2=se.lower_bound(x);
        r=*s1;s1++;r=*s1-1;
        l=*--s2;s2--;l=*s2+1;
        l=max(1,l);r=min(r,n);
        if(l!=r)
            ans=max(ans,query(root[l-1],root[r],a[i].v,31));
        se.insert(x);
    }
    printf("%d",ans);
}