首页 > 代码库 > [BZOJ 4571][Scoi2016]美味（主席树）
[BZOJ 4571][Scoi2016]美味（主席树）
Description
一家餐厅有 n 道菜，编号 1...n ，大家对第 i 道菜的评价值为 ai(1≤i≤n)。有 m 位顾客，第 i 位顾客的期
望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异或
运算。第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第
li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。
Solution
按位贪心，每次通过查询一段区间是否能够取到来判断这一位能否取最优解，主席树维护
（位运算的优先级真的非常低啊，尽量都加括号）
#include<cstdio>#include<cstdlib>#include<iostream>#include<cstring>#define N 100000#define M 200005using namespace std;int n,m,tot=0,rt[M],ls[M*20],rs[M*20],val[M*20];int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); } return x*f;} void insert(int &idx,int last,int l,int r,int v){ ++tot,idx=tot; ls[idx]=ls[last],rs[idx]=rs[last]; val[idx]=val[last]+1; if(l==r)return; int mid=(l+r)>>1; if(v<=mid)insert(ls[idx],ls[last],l,mid,v); else insert(rs[idx],rs[last],mid+1,r,v);}int query(int a,int b,int l,int r,int askl,int askr){ if(askl<=l&&askr>=r)return val[a]-val[b]; if(val[a]-val[b]==0)return 0; int mid=(l+r)>>1; if(askr<=mid)return query(ls[a],ls[b],l,mid,askl,askr); else if(askl>mid)return query(rs[a],rs[b],mid+1,r,askl,askr); else return query(ls[a],ls[b],l,mid,askl,askr)+query(rs[a],rs[b],mid+1,r,askl,askr);} int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) { int a=read(); insert(rt[i],rt[i-1],1,N,a); } for(int i=1;i<=m;i++) { int b=read(),x=read(),l=read(),r=read(),ans=0; for(int j=17;j>=0;j--) { //ans记录aj+xi能取到的最优解 int L,R; if((1<<j)&b)L=ans,R=ans|(1<<j)-1; else L=ans|(1<<j),R=ans|((1<<(j+1))-1); L=max(L-x,0),R=min(R-x,N); if(L<=R&&query(rt[r],rt[l-1],1,N,L,R)) ans|=(1<<j)*(((b>>j)&1)^1); else ans|=(1<<j)*((b>>j)&1); } printf("%d\n",ans^b); } return 0;}
[BZOJ 4571][Scoi2016]美味（主席树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。