【bzoj3166】Alo

  • 本文为博主原创,未经许可不得转载

这道题的做法值得借鉴

是这样的一个套路:遇到次大值的时候,从大到小枚举数,然后确定能选的区间,计算答案

这个用set维护就行了

然后就是用可持久化字典树处理区间最大异或和问题了

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
#define INF 1e9
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
struct node{int v,id;}a[MAXN];
int n,cnt,ans,root[MAXN],sum[MAXN*30],son[MAXN*30][2];
set<int>pos;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
bool cmp(node a,node b){return a.v>b.v;}
void insert(int &root,int last,int v){
root=++cnt; int now=root;
for(int i=30;i>=0;--i){
son[now][0]=son[last][0];
son[now][1]=son[last][1];
int x=(v&(1<<i))>>i;
son[now][x]=++cnt;
now=son[now][x];
last=son[last][x];
sum[now]=sum[last]+1;
}
}
int query(int l,int r,int v){
int ans=0;
for(int i=30;i>=0;--i){
int x=(v&(1<<i))>>i;
if(sum[son[r][x^1]]-sum[son[l][x^1]]){
ans+=(1<<i);
l=son[l][x^1];
r=son[r][x^1];
}
else l=son[l][x],r=son[r][x];
}
return ans;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read();
for(int i=1;i<=n;++i) a[i]=(node){read(),i};
for(int i=1;i<=n;++i) insert(root[i],root[i-1],a[i].v);
sort(a+1,a+n+1,cmp);
pos.insert(-1); pos.insert(-2); pos.insert(INF); pos.insert(INF+1); pos.insert(a[1].id);
for(int i=2;i<=n;++i){
set<int>::iterator it=pos.lower_bound(a[i].id); --it;
set<int>::iterator is=pos.lower_bound(a[i].id);
int l=*(--it)+1,r=*(++is)-1;
cmax(l,1); cmin(r,n);
cmax(ans,query(root[l-1],root[r],a[i].v));
pos.insert(a[i].id);
}
printf("%d\n",ans);
return 0;
}
文章目录
,