[BZOJ3166]: [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

题解

如图由左右比他大的值得到了一个区间

我们用Set维护查排名比他大1的就可以了

#include <cstdio>
#include <set>
#include <algorithm>
int n;
const int INF = 1000000000;
const int full = 30;
struct Trie
{
    struct Trie_Node
    {
        Trie_Node *ch[2];
        int s;
        Trie_Node()
        {
            ch[0] = ch[1] = NULL;
            s = 0;
        }
    } * root[100005], *null;
    Trie()
    {
        null = new Trie_Node();
        null->ch[0] = null->ch[1] = null;
        root[0] = new Trie_Node();
        root[0]->ch[1] = root[0]->ch[0] = null;
    }
    Trie_Node *NewNode()
    {
        Trie_Node *rt = new Trie_Node();
        rt->ch[0] = rt->ch[1] = null;
        return rt;
    }
    void copy(Trie_Node *&a, Trie_Node *b)
    {
        if (b == null)
            a = null;
        else
            a = NewNode(), *a = *b;
    }
    void Insert(int x, int cnt)
    {
        copy(root[cnt], root[cnt - 1]);
        Trie_Node *rt1 = root[cnt], *rt2 = root[cnt - 1];
        for (int i = full; i >= 0; i--)
        {
            int k = (x >> i) & 1;
            copy(rt1->ch[k], rt2->ch[k]);
            if (rt1->ch[k] == null)
                rt1->ch[k] = NewNode();
            rt1 = rt1->ch[k], rt2 = rt2->ch[k];
            rt1->s++;
        }
    }
    int Query(int val, int l, int r)
    {
        int res = 0;
        Trie_Node *rt1 = root[r], *rt2 = root[l - 1];
        for (int i = full; i >= 0; i--)
        {
            int next = (val >> i) & 1;
            if (rt1->ch[next ^ 1]->s - rt2->ch[next ^ 1]->s)
            {
                rt1 = rt1->ch[next ^ 1], rt2 = rt2->ch[next ^ 1];
                res |= (1 << i);
            }
            else
            {
                rt1 = rt1->ch[next], rt2 = rt2->ch[next];
            }
        }
        return res;
    }
} root;
struct data
{
    int val, i;
    bool operator < (const data &a)const 
    {
        return val > a.val;
    }
} a[50005];
std::set<int> st;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i].val);
        a[i].i = i;
    }
    for (int i = 1; i <= n; ++i)
    {
        root.Insert(a[i].val, i);
    }
    st.insert(-1), st.insert(INF), st.insert(-2), st.insert(INF + 1);
    std::sort(a + 1, a + n + 1);
    st.insert(a[1].i);
    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        int l = a[i].i, r = a[i].i;
        std::set<int>::iterator T, P;
        P = st.lower_bound(a[i].i);
        T = P;
        r = *T; T++; r = *T - 1;
        l = *--P; P--;l = *P + 1;
        l = std::max(1, l), r = std::min(r, n);
        if (l != r)
        {
            ans = std::max(ans, root.Query(a[i].val, l, r));
        }
        st.insert(a[i].i);
    }
    printf("%d", ans);
}