说在前面
me貌似已经忘记AC自动姬怎么写了 …
题目
BZOJ3166传送门
题目大意
给一串N个数字，N不超过50000。可以从中选取一段区间，并获取「这段区间的次大值 异或 这段区间除次大值之外的某个数」的收益。只能操作一次，询问最大收益。保证数字为小于1e9的非负整数，且两两不同
输入输出格式
输入格式： 第一行一个整数N，含义如题 接下来N个数，表示这一串数字
输出格式： 输出答案
解法
me一开始想偏了…想要把所有次大值提取出来然后搞事情…然而并没有什么用 于是去看了题解 对于一个数u，如果已知以u为次大值的区间为[L,R]，那么剩下的事情，就是在可持久化trie上查一下
那么考虑如何求出这个区间 先把所有数字取出，然后按照数值从大到小放回去。设u的位置为pos，那么u作为次大值的区间就是
[pos的前驱的前驱+1,pos的后继的后继−1]
[
p
o
s
的
前
驱
的
前
驱
+
1
,
p
o
s
的
后
继
的
后
继
−
1
]
。然后用set维护一下就好了
卧槽怎么那么简单？？？
下面是自带大常数的代码
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
int N , mx , ws , ans ;
struct Data{
int num , id ;
bool operator < (
const Data &A )
const {
return num > A.num ;
}
}a[
50005] ;
struct Node{
int cnt ;
Node *ch[
2] ;
}*root[
50005] ;
void newNode( Node *&nd ){
nd =
new Node() ;
nd->ch[
0] = nd->ch[
1] = NULL ;
}
void Insert( Node *las , Node *&nd ,
int dep ,
int num ){
newNode( nd ) ; nd->cnt =
1 ;
if( las ) *nd = *las , nd->cnt ++ ;
if( dep == -
1 )
return ;
if( (
1 << dep ) & num )
Insert( las ? las->ch[
1] : NULL , nd->ch[
1] , dep -
1 , num ) ;
else Insert( las ? las->ch[
0] : NULL , nd->ch[
0] , dep -
1 , num ) ;
}
int Query( Node *L , Node *R ,
int num ,
int dep ,
int ans ){
if( dep == -
1 )
return ans ;
int aim = ( num & (
1 << dep ) ) ?
0 :
1 ;
if( R->ch[aim] && ( !L || !L->ch[aim] || ( R->ch[aim]->cnt - L->ch[aim]->cnt ) ) )
return Query( L ? L->ch[aim] : NULL , R->ch[aim] , num , dep -
1 , ans + (
1 << dep ) ) ;
return Query( L ? L->ch[aim^
1] : NULL , R->ch[aim^
1] , num , dep -
1 , ans ) ;
}
void preWork(){
while( mx ) mx >>=
1 , ws ++ ; ws -- ;
for(
int i =
1 ; i <= N ; i ++ )
Insert( root[i-
1] , root[i] , ws , a[i].num ) ;
sort( a +
1 , a + N +
1 ) ;
}
set<int> S ;
void solve(){
S.insert(
0 ) ; S.insert( N +
1 ) ;
S.insert( a[
1].id ) ;
for(
int i =
2 ; i <= N ; i ++ ){
int L =
1 , R = N , pos = a[i].id ;
set<int> :: iterator it ;
if( ( it = -- S.lower_bound( pos ) ) != S.begin() ) L = *( --it ) +
1 ;
if( ( it = ++ S.lower_bound( pos ) ) != S.end() ) R = *it -
1 ;
ans = max( ans , Query( root[L-
1] , root[R] , a[i].num , ws ,
0 ) ) ;
S.insert( pos ) ;
}
printf(
"%d" , ans ) ;
}
int main(){
scanf(
"%d" , &N ) ;
for(
int i =
1 ; i <= N ; i ++ ){
scanf(
"%d" , &a[i].num ) ;
a[i].id = i , mx = max( mx , a[i].num ) ;
} preWork() ; solve() ;
}
