[SCOI2016]美味

• 这道题之前首先有一个最简化的版本，给定一个序列，求最大区间异或和。
• 首先，区间[l,r]的异或和可以是$[1,r]xor[1,l-1]$[1,r]xor[1,l−1]。我们可以维护一个前缀异或和，每次将它插入之前贪心得从高位向低位尽可能选择最优的值与当前值异或。做完以后将这个前缀插入01trie里面。
• 加强一点的：给定一个序列，多组询问，每次给定$l，r，x$l，r，x，求$a_i~xor~x$ai​ xor x的最大值，$l&lt;=i&lt;=r$l<=i<=r。这个问题做一个主席树就好了。
• 本题，给定$b,x,l,r$b,x,l,r,求$b~xor~(a_i+x)$b xor (ai​+x)的最大值。听上去好像很复杂，但其实和上个问题一样，只是查询数值范围减去一个x就好了。
• 具体来说，我们从高向低枚举每一位，假设我们匹配到了第i位，前面我们已经选了ans与b异或最大。此时这一位如果b为0，则希望找到1。查询$[ans+(1&lt;&lt;i)-x,ans+(1&lt;&lt;(i+1))-1-x]$[ans+(1<<i)−x,ans+(1<<(i+1))−1−x]是否有数，有就让ans当前位选1，否则选0。如果当前位为1，则希望找到0。查询$[ans-x,ans+(1&lt;&lt;i)-1-x]$[ans−x,ans+(1<<i)−1−x]是否有数，有就让ans当前位为0，否则为1。最后答案就是$ans~xor~b$ans xor b。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int M=1e5;
int n,m,tot,ans,b,x,l,r,a[N],sum[N*25],ls[N*25],rs[N*25],rt[N];
void update(int &o,int pre,int l,int r,int x){
	o=++tot;
	sum[o]=sum[pre]+1;
	ls[o]=ls[pre];
	rs[o]=rs[pre];
	if(l==r) return;
	int mid=l+r>>1;
	if(x<=mid) update(ls[o],ls[pre],l,mid,x);
	else update(rs[o],rs[pre],mid+1,r,x);
}
int query(int s,int t,int l,int r,int x,int y){
	if(sum[t]-sum[s]<1) return 0;
	if(l>=x&&r<=y) return sum[t]-sum[s];
	int mid=l+r>>1,tot=0;
	if(x<=mid) tot+=query(ls[s],ls[t],l,mid,x,y);
	if(y>mid) tot+=query(rs[s],rs[t],mid+1,r,x,y);
	return tot;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),update(rt[i],rt[i-1],0,M,a[i]);
	while(m--){
		scanf("%d%d%d%d",&b,&x,&l,&r);
		ans=0;int op=0;
		for(int i=20;i>=0;--i){
			if(b&(1<<i)){
				int num=query(rt[l-1],rt[r],0,M,max(0,ans-x),min(M,ans+(1<<i)-1-x));
				if(!num) ans|=(1<<i); 
			}else{
				int num=query(rt[l-1],rt[r],0,M,max(0,ans+(1<<i)-x),min(M,ans+(1<<(i+1))-1-x));
				if(num>0) ans|=(1<<i); 
			}
		}
		cout<<(ans^b)<<endl;
	}
	return 0;
}