爱悠闲 > BZOJ 3166 HEOI2013 Alo 可持久化Trie树

BZOJ 3166 HEOI2013 Alo 可持久化Trie树

分类: BZOJ  |  标签: BZOJ,BZOJ3166,可持久化Trie树  |  作者: popoqqq 相关  |  发布日期 : 2014-10-20  |  热度 : 31°

题目大意:给定一个不重复的序列a,在a中任选一个区间,求区间内的次大值与区间内的任意一个其它数的最大的异或值

首先我们枚举次大值 对于一个次大值 它可能选择的另一个数的取值范围为(l,r) 其中l为这个数左侧第二个比它大的数 r为这个数右侧第二个比它大的数

在这个区间内的Trie树中贪心寻找最大值即可

这个区间怎么求呢?我们维护一棵平衡树 将数从大到小将下标加进平衡树 每加进一个下标 比它大的数的下标都在平衡树中 求两次后继就是r 求两次前驱就是l

我偷懒写了set……

#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 50500
#define ls son[0]
#define rs son[1]
using namespace std;
struct Trie{
	Trie *son[2];
	int cnt;
}*tree[M],mempool[M*40],*C=mempool;
int n,maxnum,ans,a[M],l[M],r[M];
pair<int,int>b[M];
set<int>s;
set<int>::iterator it;
inline Trie* New_Node(Trie *_,Trie *__,int ___)
{
	C->ls=_;
	C->rs=__;
	C->cnt=___;
	return C++;
}
Trie* Build_Tree(Trie *p,int x,int pos)
{
	if(!pos)
		return New_Node(0x0,0x0,p->cnt+1);
	if(~x&pos)
		return New_Node(Build_Tree(p->ls,x,pos>>1),p->rs,p->cnt+1);
	else
		return New_Node(p->ls,Build_Tree(p->rs,x,pos>>1),p->cnt+1);
}
int Get_Ans(Trie *l,Trie *r,int x,int pos)
{
	int num=x&pos?1:0;
	if(!pos)
		return 0;
	if(r->son[!num]->cnt-l->son[!num]->cnt)
		return pos + Get_Ans(l->son[!num],r->son[!num],x,pos>>1);
	else
		return Get_Ans(l->son[num],r->son[num],x,pos>>1);
}
inline int Get_L(int x)
{
	it=s.find(x);
	if(it--==s.begin()) return 0;
	if(it--==s.begin()) return 0;
	return *it;
}
inline int Get_R(int x)
{
	it=s.find(x);
	if(++it==s.end()) return n+1;
	if(++it==s.end()) return n+1;
	return *it;
}
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i].first=a[i];
		b[i].second=i;
		maxnum=max(maxnum,a[i]);
	}
	sort(b+1,b+n+1);
	for(i=n;i;i--)
	{
		s.insert(b[i].second);
		l[b[i].second]=Get_L(b[i].second);
		r[b[i].second]=Get_R(b[i].second);		
	}
	tree[0]=New_Node(C,C,0);
	for(i=1;i<=n;i++)
		tree[i]=Build_Tree(tree[i-1],a[i],1<<30);
	for(i=1;i<=n;i++)
		if(a[i]!=maxnum)
			ans=max(Get_Ans(tree[l[i]],tree[r[i]-1],a[i],1<<30),ans);
	cout<<ans<<endl;
}