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 道中选择。请你帮助他们找出最美味的菜。

Input 第1行，两个整数，n，m，表示菜品数和顾客数。 第2行，n个整数，a1，a2，…，an，表示每道菜的评价值。 第3至m+2行，每行4个整数，b，x，l，r，表示该位顾客的期望值，偏好值，和可以选择菜品区间。 1≤n≤2×10^5，0≤ai,bi,xi＜10^5，1≤li≤ri≤n(1≤i≤m)；1≤m≤10^5

Output

输出 m 行，每行 1 个整数，ymax ，表示该位顾客选择的最美味的菜的美味值。 Sample Input 4 4 1 2 3 4 1 4 1 4 2 3 2 3 3 2 3 3 4 1 2 4 Sample Output 9 7 6 7 HINT

Source

这种问题 一般都是在trie树上进行贪心 然而这题有加减的一个操作 所以并不能在trie树上贪心 考虑按照权值建立 主席树 然后每次按位贪心 贪心的看一看主席树上我这段区间减去x之后的位置有没有数 有的话就继续 反之 这一位上不能贪心 然后一步一步把前面确定的位置确定好即可

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;} const int N=2e5+10;struct node{ int left,right,s;}tree[N*22];int num,n,m,rt[N];inline void insert1(int &x,int l,int r,int p){ tree[++num]=tree[x];x=num;++tree[x].s; if (l==r) return;int mid=l+r>>1; if (p<=mid) insert1(tree[x].left,l,mid,p); if (p>mid) insert1(tree[x].right,mid+1,r,p);}inline bool query(int rt1,int rt2,int l,int r,int l1,int r1){ if (!rt2) return 0; if (l1<=l&&r1>=r){return (tree[rt2].s-tree[rt1].s)>0;}int mid=l+r>>1,p=0; if (l1<=mid) p|=query(tree[rt1].left,tree[rt2].left,l,mid,l1,r1);if (p) return p; if (r1>mid) p|=query(tree[rt1].right,tree[rt2].right,mid+1,r,l1,r1);return p;}int main(){ freopen("bzoj4571.in","r",stdin); n=read();m=read(); for (int i=1;i<=n;++i){ int a=read();rt[i]=rt[i-1];insert1(rt[i],0,1e5,a); } for (int owo=1;owo<=m;++owo){ int b=read(),x=read(),l=read(),r=read(),lim=0,ans=0; for (int i=17;~i;--i){ if ((1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。