注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3166][Heoi2013]Alo  

2015-03-19 11:18:10|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3166: [Heoi2013]Alo

一开始想错了Q.Q
题面虽然叫ALO但是似乎没有半毛钱关系
题解在代码下方

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 50000+100;
const int LOGN = 33;
int n,m,data[N],mx[N][2][2],cp[N],rk[N],two[50];
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
int tree[N][2],type;
void update(int re[2],int val){
if(!type){
if(val > re[0]){
re[1]=re[0];
re[0]=val;
}else if(val > re[1])re[1]=val;
}else{
if(val < re[0]){
re[1]=re[0];
re[0]=val;
}else if(val < re[1])re[1]=val;
}
}
void push(int x,int val){
for(;x;x-=x&-x)update(tree[x],val);
}
void get(int x,int re[2]){
if(!type)re[0]=re[1]=0;else re[0]=re[1]=2e9;
for(;x<=cp[0]+1;x+=x&-x)
update(re,tree[x][0]),
update(re,tree[x][1]);
}
void clear(int val=2e9){for(int i=1;i<=cp[0];i++)tree[i][0]=tree[i][1]=val;}

int T,tn[N],tval[N*LOGN],ch[N*LOGN][2];
int tpush(int odr,int x){
int re=++T,ro=re;
tval[ro]=tval[odr]+1;
for(int i=30;i>=0;i--){
int c = (x&two[i])!=0;
ch[ro][c^1] = ch[odr][c^1];
odr=ch[odr][c];
ro=ch[ro][c]=++T;
tval[ro]=tval[odr]+1;
}
return re;
}
int ask(int lr,int rr,int x){
int re=0;
for(int i=30;i>=0;i--){
int c = (x&two[i])!=0;
if(tval[ch[rr][c^1]]-tval[ch[lr][c^1]]>0){
lr = ch[lr][c^1];
rr = ch[rr][c^1];
re += two[i];
}else{
lr = ch[lr][c];
rr = ch[rr][c];
}
}
return re;
}
int main(){
int i,j;
//printf("%d\n",9^15);
freopen("in.txt","r",stdin);
n=scan();
for(two[0]=1,i=1;i<=30;i++)two[i]=two[i-1]*2;
for(i=1;i<=n;i++)cp[i]=data[i]=scan();
sort(cp+1,cp+1+n);
cp[n+1] = 2e9;
cp[0]=n+1;
for(i=1;i<=n;i++)rk[i] = lower_bound(cp+1,cp+1+cp[0],data[i])-cp;
//for(i=1;i<=n;i++)printf("%d ",rk[i]);printf("\n");
rk[0]=rk[n+1] = n+1;
clear(-1);
push(cp[0]+1,0);
for(i=1;i<=n;i++){
get(rk[i],mx[i][0]);
push(rk[i],i);
}
clear();type=1;
push(cp[0]+1,n+1);
for(i=n;i;i--){
get(rk[i],mx[i][1]);
push(rk[i],i);
}

//for(i=1;i<=n;i++)printf("%d ",mx[i][0]);printf("\n");
//for(i=1;i<=n;i++)printf("%d ",mx[i][1]);printf("\n");

//make trie
for(i=1;i<=n;i++)tn[i] = tpush(tn[i-1],data[i]);
int ans = -1;
//printf("(%d)\n\n",ask(tn[0],tn[5],data[5]));

for(i=1;i<=n;i++){
//left
//printf("[%d]\n",i);
if(mx[i][0][0]!=0){
//printf("(%d %d]\n",mx[ mx[i][0] ][0],mx[i][1]-1);
j = ask(tn[ max(mx[ mx[i][0][0] ][0][0],mx[i][0][1]) ], tn[mx[i][1][0]-1],data[i]);
/*
if(j==15){
printf("[0]%d %d %d\n",i,mx[i][0],mx[i][1]);
printf("(%d %d]\n",mx[ mx[i][0] ][0],mx[i][1]-1);
}*/
ans = max(ans,j);
}
//right
if(mx[i][1][0]!=n+1){
//printf("(%d %d]\n",mx[i][0],mx[ mx[i][1] ][1]-1);
/*
if(j==15){
printf("[1]%d %d %d\n",i,mx[i][0],mx[i][1]);
}*/
j = ask(tn[ mx[i][0][0] ], tn[ min(mx[ mx[i][1][0] ][1][0],mx[i][1][1] )-1 ],data[i]);
ans = max(ans,j);
}
}
printf("%d\n",ans);
return 0;
}

题解:
如果对于一个数i我们知道它在哪个区间里是次大值,那么我们就可以在这个区间里直接用trie贪心了。
所以用树状数组预处理出每个位置i左右两边比它大的两个数的位置
mx[i][0][0]和mx[i][0][1]表示i左边的两个数
mx[i][1][0]和mx[i][1][1]表示右边的两个
然后尽可能大的两个区间就是
( max(mx[ mx[i][0][0] ][0][0],mx[i][0][1]), mx[i][1][0]-1 ]
( mx[i][0][0], min(mx[ mx[i][1][0] ][1][0],mx[i][1][1] )-1 ]
  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017