[bzoj] 3166: [Heoi2013]Alo

发表于   |   分类于   |  

题意

给定一个序列,选择一个区间,使得区间第二大的数与区间内其它的数字按位异或得到的结果的最大值最大.

传送门

分析

我们求出将每一个数字作为第二大的数时,向左向右最远能扩展到多少.
再按照输入顺序给序列做可持久化Trie,这棵Trie表示每个数字二进制下每一位的0或1.
于是我们就根据可持久化数据结构的可减性找到任意一个区间的Trie的形态.
将每一个数在它所应属的区间的Trie树上求答案即可.
因为一个数与自己按位异或得到结果为0,所以第二大的数在这个区间内也没有影响.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <algorithm>
#include <set>

#define  maxn  55000LL
#define  maxd  31LL

struct GEM {
trueint num , id ;
truebool operator < (const GEM& b) const
true{ return num < b.num ; }
} a[maxn] ;

struct Trie {
trueTrie *c[2] ;
trueint sum ;
} nodes[maxn*80] ;
Trie *root[maxn] , *null ;
int tot = 0 ;

void BuildTrie() {
trueroot[0] = null = &nodes[tot++] ;
truenull->c[0] = null->c[1] = null ;
truenull->sum = 0 ;
}

void Insert(Trie *rt1 , Trie *rt2 , int num , int d) {
true*rt2 = *rt1 ; rt2->sum ++ ;
trueif (d < 0) return ;
trueif ((num>>d)&1) {
truetruert2->c[1] = &nodes[tot++] ;
truetrueInsert(rt1->c[1] , rt2->c[1] , num , d-1) ;
true} else {
truetruert2->c[0] = &nodes[tot++] ;
truetrueInsert(rt1->c[0] , rt2->c[0] , num , d-1) ;
true}
}

int Query(Trie *rt1 , Trie *rt2 , int num , int d) {
trueif (d < 0) return 0 ;
trueint p = (num>>d)&1 ;
trueif (rt2->c[p^1]->sum - rt1->c[p^1]->sum)
truetruereturn (1<<d)+Query(rt1->c[p^1],rt2->c[p^1],num,d-1) ;
trueelse return Query(rt1->c[p],rt2->c[p],num,d-1) ;
}

int l1[maxn] , l2[maxn] , r1[maxn] , r2[maxn] , num[maxn] ;

std::multiset<int>S ;
std::multiset<int>::iterator left , right ;

int n , ans ;
int main() {
int i ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) ;
trueRep (i,1,n)
truetrueread(a[i].num) ,
truetruenum[i] = a[i].num ,
truetruea[i].id = i ;
truestd::sort(a+1 , a+n+1) ;
trueS.insert(n+1) ; S.insert(n+1) ;
trueS.insert(0) ; S.insert(0) ;
trueRev (i,n,1) {
truetrueS.insert(a[i].id) ;
truetrueleft = right = S.lower_bound(a[i].id) ;
truetrueleft -- ; l2[a[i].id] = *left ;
truetrueleft -- ; l1[a[i].id] = *left ;
truetrueright ++ ; r2[a[i].id] = *right ;
truetrueright ++ ; r1[a[i].id] = *right ;
true}
trueBuildTrie() ;
trueRep (i,1,n)
truetrueroot[i] = &nodes[tot++] ,
truetrueInsert(root[i-1] , root[i] , num[i] , maxd) ;
trueans = 0 ;
trueRep (i,1,n) {
truetrueif (r2[i]==n && l2[i]==0) continue ;
truetrueans = std::max(ans , Query(root[l1[i]],root[r1[i]-1],num[i],maxd)) ;
true}
trueprintf("%d\n", ans) ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章