[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);
}