首页 > 其他 > 详细

bzoj 3166: [Heoi2013]Alo

时间:2014-05-07 20:30:05      阅读:421      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 55000
#define inf 0x3fffffff
int ind[N];
int n,a[N];
int b1[N],b2[N];
int qu[N],he;
int l[N],r[N];
int tot;
int c[N*80][2];
int siz[N*80];
struct P{
    int x,y;
    bool operator<(P a)const{
        return y<a.y; 
    }
}b[N];
int build(int p,int y,int u){
    int x=++tot;
    siz[x]=siz[p]+1;
    if(!u)return x;    
    c[x][0]=c[p][0];
    c[x][1]=c[p][1];    
    if((1<<u-1)&y){
        c[x][1]=build(c[p][1],y,u-1);
    }else{
        c[x][0]=build(c[p][0],y,u-1);
    }
    return x;
}
int ss;
int maxx;
int sm[N];
void ask(int L,int R,int y,int u){
    if(!u)return;
    int k=1;
    if((1<<u-1)&y)k=0;
    if(siz[c[R][k]]-siz[c[L][k]]){
        ss+=(1<<u-1);
        ask(c[L][k],c[R][k],y,u-1);
    }else ask(c[L][!k],c[R][!k],y,u-1);
}
void dele(int x){
   if(b1[x])b2[b1[x]]=b2[x];
    if(b2[x])b1[b2[x]]=b1[x];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=(P){i,a[i]};
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)b1[i]=i-1,b2[i]=i+1;
    b2[n]=0;
    int mi=0;
     mi=b[n].y;
     for(int i=1;i<=n;i++){
         l[b[i].x]=b1[b1[b[i].x]],r[b[i].x]=b2[b2[b[i].x]];
         dele(b[i].x);
     }
      for(int i=1;i<=n;i++){
        ind[i]=build(ind[i-1],a[i],31);
    }
    for(int i=1;i<=n;i++){
        if(mi==a[i])continue;
        if(!r[i])r[i]=n+1;
        ss=0;
        ask(ind[l[i]],ind[r[i]-1],a[i],31);
        maxx=max(maxx,ss);
    }
    cout<<maxx;
}
bubuko.com,布布扣

 

bzoj 3166: [Heoi2013]Alo,布布扣,bubuko.com

bzoj 3166: [Heoi2013]Alo

原文:http://www.cnblogs.com/wangyucheng/p/3714149.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!