首页 > 代码库 > bzoj3166[HEOI2013]ALO
bzoj3166[HEOI2013]ALO
AlfheimOnline == Arithmetic and Logistic Online
题意:给你一个长为n的序列,序列中一个长度大于1的区间的价值定义为这个区间中的次大值和这个区间中其他任意一个值异或的最大值,求所有区间的价值中的最大值.n<=50000
如果知道某个数作为次大值可以和哪些数字进行异或,那么在可持久化字典树上查询就好了.发现某个数字作为次大值能够影响的数字是直到左边第二个比它大的数和右边第二个比它大的数.
”左/右边第二个比它大的数的位置”只需要建立一棵主席树然后二分就可以nlog^2n时间内解决了(有nlogn的做法…不过我脑子不太好使就主席树直接上了…n=50000不虚)。注意如果一个数字是所有数字中最大的则不能向其他数字做出贡献.
主席树和可持久化字典树的节点可以用同一个结构体倒是很愉悦.
#include<cstdio> #include<algorithm> #include<queue> using namespace std; const int maxn=50005; struct node{ int sum;node* ch[2]; node(){} node(int x){sum=x;ch[0]=ch[1]=0;} }t[maxn*50];int tot=0; node* newnode(int x){ t[++tot]=node(x);return t+tot; } node* root[maxn]; int n; int l[maxn],r[maxn]; int seq[maxn],a[maxn],b[maxn]; bool cmp(const int &x,const int &y){ return a[x]<a[y]; } //persistable weight segment tree void Insert1(node* rt0,node* &rt,int l,int r,int x){ rt=newnode(rt0->sum+1); if(l==r)return; int mid=(l+r)>>1; if(x<=mid){ Insert1(rt0->ch[0],rt->ch[0],l,mid,x); rt->ch[1]=rt0->ch[1]; }else{ Insert1(rt0->ch[1],rt->ch[1],mid+1,r,x); rt->ch[0]=rt0->ch[0]; } } int query(node* rt0,node* rt1,int l,int r,int ql){ if(l==r)return rt1->sum-rt0->sum; int mid=(l+r)>>1; int ans=0; if(ql>mid)return query(rt0->ch[1],rt1->ch[1],mid+1,r,ql); return query(rt0->ch[0],rt1->ch[0],l,mid,ql)+rt1->ch[1]->sum-rt0->ch[1]->sum; } int binary1(int l,int r,int pos,int x){ while(l<=r){ int mid=(l+r)>>1; if(query(root[mid-1],root[pos-1],1,n,x)>=2)l=mid+1; else r=mid-1; } return l-1; } int binary2(int l,int r,int pos,int x){ while(l<=r){ int mid=(l+r)>>1; if(query(root[pos],root[mid],1,n,x)>=2)r=mid-1; else l=mid+1; } return r+1; } void init(){ for(int i=1;i<=n;++i)seq[i]=i; sort(seq+1,seq+n+1,cmp); for(int i=1;i<=n;++i)b[seq[i]]=i; root[0]=t+0;root[0]->sum=0;root[0]->ch[0]=root[0]->ch[1]=t+0; for(int i=1;i<=n;++i)Insert1(root[i-1],root[i],1,n,b[i]); for(int i=1;i<=n;++i){ l[i]=binary1(1,i-1,i,b[i]);r[i]=binary2(i+1,n,i,b[i]); } } //persistable trie void Insert2(node* rt0,node* &rt,int x,int depth){ rt=newnode(rt0->sum+1); if(depth==-1)return; int t=(x>>depth)&1; Insert2(rt0->ch[t],rt->ch[t],x,depth-1); rt->ch[t^1]=rt0->ch[t^1]; } int query2(node* rt0,node *rt1,int x,int depth){ if(depth==-1)return 0; int t=(x>>depth)&1; if(rt1->ch[t^1]->sum!=rt0->ch[t^1]->sum){ return (1<<depth)|query2(rt0->ch[t^1],rt1->ch[t^1],x,depth-1); }else{ return query2(rt0->ch[t],rt1->ch[t],x,depth-1); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&a[i]); init(); tot=0; for(int i=1;i<=n;++i)Insert2(root[i-1],root[i],a[i],31); int ans=0; for(int i=1;i<=n;++i){ if(b[i]==n)continue; ans=max(ans,query2(root[l[i]],root[r[i]-1],a[i],31)); } printf("%d\n",ans); return 0; }
bzoj3166[HEOI2013]ALO
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。