BZOJ3166: [Heoi2013]Alo

题解:stl 找到当前值从右往左第二个比他大的值从左往右第二个比他大的值然后对这个区间查询可持久化trie即可

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=5e4+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

typedef struct node{
	int l,r,sum;
}node;
node d[31*MAXN];
int rt[MAXN],cnt;
void insert(int x,int k){
	for(int i=29;i>=0;i--){
		if(k&(1<<i)){
			int t=++cnt;d[t]=d[d[x].r];d[x].r=t;d[t].sum++;
			x=t;
		}
		else{
			int t=++cnt;d[t]=d[d[x].l];d[x].l=t;d[t].sum++;
			x=t;
		}
	}
}
int querty(int x,int y,int k){
	int res=0;
	for(int i=29;i>=0;i--){
		if(k&(1<<i)){
			if(d[d[y].l].sum-d[d[x].l].sum)x=d[x].l,y=d[y].l;
			else res+=(1<<i),x=d[x].r,y=d[y].r;
		}
		else{
			if(d[d[y].r].sum-d[d[x].r].sum)res+=(1<<i),x=d[x].r,y=d[y].r;
			else x=d[x].l,y=d[y].l;
		}
	}
	return (res^k);
}
set<int>s;
set<int>::iterator ite,ip;
typedef struct Tmp{
	int id,vul;
	friend bool operator<(Tmp aa,Tmp bb){return aa.vul>bb.vul;}
}Tmp;
Tmp a[MAXN];	
int main(){
	int n;n=read();cnt=0;
	rt[0]=++cnt;insert(rt[0],0);
	inc(i,1,n)a[i].vul=read(),a[i].id=i,rt[i]=++cnt,d[rt[i]]=d[rt[i-1]],insert(rt[i],a[i].vul);
	sort(a+1,a+n+1);
	int ans=querty(rt[0],rt[n],a[2].vul);
	s.insert(a[1].id);s.insert(a[2].id);
	inc(i,3,n){
		int l,r;
		ite=s.lower_bound(a[i].id);ip=s.end();ip--;
		if(ite==s.end()||ite==ip)r=n;
		else ite++,r=(*ite)-1,ite--;
		ip=s.begin();ip++;
		if(ite==s.begin()||ite==ip)l=1;
		else ite--,ite--,l=(*ite)+1;
		ans=max(ans,querty(rt[l-1],rt[r],a[i].vul));
		s.insert(a[i].id);
	}
	printf("%d
",ans);
}

3166: [Heoi2013]Alo

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 1335 Solved: 628
[Submit][Status][Discuss]

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