题目描述
一家餐厅有 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
Solution：
本题伪trie树真主席树。
题目很容易让人往可持久化trie上想，然后就gg了。
查询区间是否存在某数，想到用主席树实现。
我们对于每次询问，设置查询的值域区间$[L,R]$（初始$L=0,R=2^{18}-1$），那么还是贪心由$b$从高位往低位判断， 若第$i$位为$1$，则我们要查询在$[l,r]$中是否存在$[L-x,R-x-2^i]$范围内的数（这些数显然$+x$后第$i$位为$0$），然后根据查询情况调整值域区间的范围，第$i$位为$0$情况同理分析就好了。
代码：
/*Code by 520 -- 9.30*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=;
int n,m,a[N],rt[N],cnt,maxn;
struct node{
int ls,rs,tot;
}t[N*]; int gi(){
int a=;char x=getchar();
while(x<''||x>'') x=getchar();
while(x>=''&&x<='') a=(a<<)+(a<<)+(x^),x=getchar();
return a;
} il void up(int rt){t[rt].tot=t[t[rt].ls].tot+t[t[rt].rs].tot;} void ins(int v,int l,int r,int lst,int &rt){
t[rt=++cnt]=t[lst];
if(l==r) {t[rt].tot++;return;}
int m=l+r>>;
if(v<=m) ins(v,l,m,t[lst].ls,t[rt].ls);
else ins(v,m+,r,t[lst].rs,t[rt].rs);
up(rt);
} int query(int L,int R,int l,int r,int lst,int rt){
if(R<||L>maxn) return ;
if(L<=l&&R>=r) return t[rt].tot-t[lst].tot;
int m=l+r>>,sum=;
if(L<=m) sum+=query(L,R,l,m,t[lst].ls,t[rt].ls);
if(R>m) sum+=query(L,R,m+,r,t[lst].rs,t[rt].rs);
return sum;
} int main(){
n=gi(),m=gi();
For(i,,n) a[i]=gi(),maxn=max(maxn,a[i]);
memset(&t[],,sizeof(t[]));
For(i,,n) ins(a[i],,maxn,rt[i-],rt[i]);
int b,x,l,r,L,R;
while(m--){
b=gi(),x=gi(),l=gi(),r=gi();
L=,R=(<<)-;
Bor(i,,)
if(b&(<<i)){
if(query(L-x,R-(<<i)-x,,maxn,rt[l-],rt[r])) R-=(<<i);
else L+=(<<i);
}
else {
if(query(L+(<<i)-x,R-x,,maxn,rt[l-],rt[r])) L+=(<<i);
else R-=(<<i);
}
printf("%d\n",L^b);
}
return ;
}