( ext{Solution:})
第一种感觉是可持久化 Trie 的样子。但是如果这样做， (x) 的限制是没有办法消去的。
这里陷入了某种错误的思考状态，发现 Trie 上分类讨论无果，从题解中学到了另一种做法：
Trie 树的本质是每一个节点下的子树都代表了一个值域。我们联想到，主席树同样可以是值域线段树，它也可以代表一个值域。
那能不能用更普遍的主席树去代替 Trie 呢？
考虑对于 (b) 的某二进制位的取值， (a[i]) 应该取什么。
那么，若 (b) 的第 (i) 位为 (1) 那么 (a[i]) 这一位是 (0) 更优秀。
那么，令当前找到的最优结果是 (A,) (ain{[A-x,A+(1<<i)-1-x]}) 这样使得 (a+x) 的对应二进制位一定非 (1).
其他情况类似。
那么我们就得到了需要的 (a) 的值域！ 而前文我们恰好对 (a) 以值域建立了主席树。
于是，在主席树上查询即可。复杂度 (O(mlog^2 v).)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
const int M=(1<<25);
struct Tr{int ls,rs,sum;}tr[MAXN<<5];
int node,rt[MAXN],n,m,a[MAXN];
inline int Min(int x,int y){return x<y?x:y;}
inline int Max(int x,int y){return x>y?x:y;}
inline int read() {
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-')w=-1;
ch=getchar();
}
while(isdigit(ch)) {
s=s*10-48+ch;
ch=getchar();
}
return w*s;
}
int change(int x,int l,int r,int pos,int v){
int p=++node;
tr[p]=tr[x];
tr[p].sum+=v;
if(l==r)return p;
int mid=(l+r)>>1;
if(pos<=mid)tr[p].ls=change(tr[p].ls,l,mid,pos,v);
else tr[p].rs=change(tr[p].rs,mid+1,r,pos,v);
return p;
}
int query(int x,int y,int L,int R,int l,int r){
if(L>=l&&R<=r)return tr[y].sum-tr[x].sum;
int mid=(L+R)>>1,res=0;
if(l<=mid)res=query(tr[x].ls,tr[y].ls,L,mid,l,r);
if(mid<r)res+=query(tr[x].rs,tr[y].rs,mid+1,R,l,r);
return res;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)rt[i]=change(rt[i-1],0,M,a[i],1);
for(int i=1;i<=m;++i){
int b=read(),x=read(),l=read(),r=read();
int ans=0;
for(int j=23;j>=0;--j){
int L=0,R=M,flag;
if((b>>j)&1)L=ans,R=ans+(1<<j)-1,flag=0;
else L=ans+(1<<j),R=ans+(1<<(j+1))-1,flag=1;
L-=x;R-=x;
L=Max(L,0);R=Min(R,M);
if(!query(rt[l-1],rt[r],0,M,L,R))flag^=1;//the direction of node
ans+=(flag<<j);
}
printf("%d
",ans^b);
}
return 0;
}