题目
题目描述
一家餐厅有 n 道菜，编号 1…n ，大家对第 i 道菜的评价值为 ai(1<=i<=n)。有 m 位顾客，第 i 位顾客的期望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异或运算。
第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。
输入输出格式
输入格式：
第1行，两个整数，n，m，表示菜品数和顾客数。
第2行，n个整数，a1，a2，…，an，表示每道菜的评价值。
第3至m+2行，每行4个整数，b，x，l，r，表示该位顾客的期望值，偏好值，和可以选择菜品区间。
输出格式：
输出 m 行，每行 1 个整数，ymax ，表示该位顾客选择的最美味的菜的美味值。
输入输出样例
输入样例#1：
4 4
1 2 3 4
1 4 1 4
2 3 2 3
3 2 3 3
4 1 2 4
输出样例#1：
9
7
6
7
说明
对于所有测试数据，1<=n<=2*10^5，0<=ai,bi,xi＜10^5，1<=li<=ri<=n(1<=i<=m)；1<=m<=10^5
题解
如果没有$x$，就可以直接可持久化$Trie$贪心了，现在可以来模拟这个贪心的过程
从高到低枚举二进制位，假设贪心到了第$k$位，$b$的第$k$位为$1$，答案的第$k$位最优应该放$0$，所以只要查找区间$[l,r]$里是否存在数在$[ans-x,ans-x+(1«k)-1]$之间，保证加上$x$后这一位为$0$，$ans$是之前位贪心的结果，不影响当前位
判断是否存在就可以用主席树了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct p{
int x,l,r;
}s[MAX<<5];
int n,m,mx,tot;
int a[MAX],rt[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void change(int l,int r,int &k,int pre,int x)
{
s[k=++tot]=s[pre],++s[k].x;
if(l==r) return;
if(x<=mid) change(l,mid,tl,s[pre].l,x);
else change(mid+1,r,tr,s[pre].r,x);
}
bool ask(int l,int r,int k,int pre,int L,int R)
{
if(r<L||R<l) return 0;
if(l>=L&&r<=R) return s[pre].x-s[k].x;
if(ask(l,mid,tl,s[pre].l,L,R)) return 1;
return ask(mid+1,r,tr,s[pre].r,L,R);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
a[i]=read(),mx=max(mx,a[i]);
for(int i=1;i<=n;++i)
change(0,mx,rt[i],rt[i-1],a[i]);
for(int i=1,b,l,r,x,ans;i<=m;++i)
{
b=read(),x=read(),l=read(),r=read(),ans=0;
bool o;
for(int i=17;i>=0;--i)
{
o=bool(b&(1<<i))^1;
if(ask(0,mx,rt[l-1],rt[r],ans+o*(1<<i)-x,min(ans+(o+1)*(1<<i)-1-x,mx))) ans+=o*(1<<i);
else ans+=(o^1)*(1<<i);
}
printf("%d\n",ans^b);
}
return 0;
}
