4571: [Scoi2016]美味
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 656 Solved: 350
[Submit][Status][Discuss]
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
三步走
●维护xor最大值的话用trie树可以搞一搞
●维护区间xor最大值可以用可持久化trie树
●维护区间xor并支持加减的就是可持久化权值线段树了，这就是本题的算法，用贪心+主席树实现
贪心？肯定先确定最高位使得xor后此位为1，由此得到
策略1：从二进制高位向低位贪心，尽量满足 b的i位与（a[j]+x）的i位不同
怎么判断第i位是否可以不同？可以假设（a[j]+x）的i位与b的i位不同，来确定所选的数的第i位，再判定假设是否合法。
合法的条件是什么？记已确定的数为ans，只用查找区间内是否存在数这样的满足条件
1.前面位和ans相同
2.此位满足已确定的数
不太容易懂，举一个例子：
假设b的当前位为1，我们应尽量使a[j]+x当前位为0，前面位确定为ans，ans第i位设定为0，查找区间内是否存在 在[ans,ans+(1<<i)-1]之内的数，如果有，则此位可以为0
判断区间的数的个数，权值线段树
但此时我们注意到查找是双关键字的，一个是区间一个是权值，所以用主席树来完成操作
总结得出
策略2：用主席树判断区间数的存在性问题来确定当前位究竟是什么
到了这里，此题也就差不多了，但有几个细节需要注意
●主席树空间开够（我就是这里错了好久--为什么dev不报RE而是乱搞数组啊！！）
●由于我们查询的数是a[j]+x，而树中插入的是a[]，所以查询区间统一减去x并考虑区间是否超界
●最后注意，我们的到的ans是选出来的数，所以输出时要xor b
没有了-------------------------------------------------------------------
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long
#define N 200005
#define mx (1<<18)-1
using namespace std;
int n,m,a[N],rt[N],ls[N<<5],rs[N<<5],sum[N<<5],sz;
void insert(int pre,int &u,int l,int r,int pos){
u=++sz;ls[u]=ls[pre];rs[u]=rs[pre];sum[u]=sum[pre]+1;
if(l==r)return;int mid=(l+r)>>1;
if(pos<=mid)insert(ls[pre],ls[u],l,mid,pos);
else insert(rs[pre],rs[u],mid+1,r,pos);
}
int query(int pre,int u,int l,int r,int L,int R){
if(L<=l&&r<=R)return sum[u]-sum[pre];
int mid=(l+r)>>1;int t=0;
if(L<=mid)t+=query(ls[pre],ls[u],l,mid,L,R);
if(R>mid)t+=query(rs[pre],rs[u],mid+1,r,L,R);
return t;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
insert(rt[i-1],rt[i],0,mx,a[i]);
for(int i=1;i<=m;i++){
int b,x,l,r;
scanf("%d%d%d%d",&b,&x,&l,&r);
int ans=0;
for(int j=17;j>=0;j--){
if(b&(1<<j)){
int L=max(ans-x,0),R=ans+(1<<j)-x-1;
if(R<0||!query(rt[l-1],rt[r],0,mx,L,R))ans^=(1<<j);
}
else{
ans^=(1<<j);
int L=max(ans-x,0),R=ans+(1<<j)-x-1;
if(R<0||!query(rt[l-1],rt[r],0,mx,L,R))ans^=(1<<j);
}
}
printf("%d
",ans^b);
}
return 0;
}