题目描述
一家餐厅有 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=200005; int n,m,a[N],rt[N],cnt,maxn; struct node{ int ls,rs,tot; }t[N*40]; int gi(){ int a=0;char x=getchar(); while(x<'0'||x>'9') x=getchar(); while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),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>>1; if(v<=m) ins(v,l,m,t[lst].ls,t[rt].ls); else ins(v,m+1,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<0||L>maxn) return 0; if(L<=l&&R>=r) return t[rt].tot-t[lst].tot; int m=l+r>>1,sum=0; if(L<=m) sum+=query(L,R,l,m,t[lst].ls,t[rt].ls); if(R>m) sum+=query(L,R,m+1,r,t[lst].rs,t[rt].rs); return sum; } int main(){ n=gi(),m=gi(); For(i,1,n) a[i]=gi(),maxn=max(maxn,a[i]); memset(&t[0],0,sizeof(t[0])); For(i,1,n) ins(a[i],0,maxn,rt[i-1],rt[i]); int b,x,l,r,L,R; while(m--){ b=gi(),x=gi(),l=gi(),r=gi(); L=0,R=(1<<18)-1; Bor(i,0,17) if(b&(1<<i)){ if(query(L-x,R-(1<<i)-x,0,maxn,rt[l-1],rt[r])) R-=(1<<i); else L+=(1<<i); } else { if(query(L+(1<<i)-x,R-x,0,maxn,rt[l-1],rt[r])) L+=(1<<i); else R-=(1<<i); } printf("%d ",L^b); } return 0; }