[bzoj4571]-[SCOI2016]美味

题目（BZOJ）
题目（洛谷）
 
来说说这题吧~
首先题目是要求异或和最大，然后再看数据范围：都是1e5以内，由于(1<<17)=131,072明显大于1e5，又没有修改操作，所以我们考虑贪心来求。
前面的b是给定的，我们来考虑后面的式子：aj+x
我们从高到低贪心二进制每一位，看这一位异或上b在[l,r]内能否为1，也就是说看在[l,r]内是否存在(aj+x)的这一位与b的这一位不相等。
所以，我们可以对[0,(1<<18)-1]建一棵权值线段树（注意可能这17位上每一位都为1），这棵线段树用来维护aj（x每次给定，可以不维护），在值域[max(0,ans-x), ans+(1<<i)-1-x]上查找该数即可。
考虑差分，查找[l,r]内是否存在就是看sum[r]-sum[l-1]是否等于0，如果不等于就说明找到了，等于就说明这个区间内没有这个数。
这个用主席树就可以解决。

#include <bits/stdc++.h>
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=200050;
const int M=(1<<18)+5;
const int maxm=(1<<18)-1;
int n,m,rt[N];
int ls[M*20],rs[M*20],sz[M*20],tsz;
void insert(int l,int r,int x,int &y,int v){
	y=++tsz;sz[y]=sz[x]+1;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(v<=mid)rs[y]=rs[x],insert(l,mid,ls[x],ls[y],v);
	else ls[y]=ls[x],insert(mid+1,r,rs[x],rs[y],v);
}
int query(int l,int r,int x,int y,int L,int R){
	if(l==L&&r==R)return sz[y]-sz[x];
	int mid=(l+r)>>1;
	if(R<=mid)return query(l,mid,ls[x],ls[y],L,R);
	else if(L>mid)return query(mid+1,r,rs[x],rs[y],L,R);
	else return query(l,mid,ls[x],ls[y],L,mid)+query(mid+1,r,rs[x],rs[y],mid+1,R);
}
int main(){
	read(n),read(m);
	for(int i=1;i<=n;++i){
		int x;read(x);
		insert(0,maxm,rt[i-1],rt[i],x);
	}
	while(m--){
		int b,x,l,r,ans=0;
		read(b),read(x),read(l),read(r);l--;
		for(int i=17;i>=0;--i){
			if(!((1<<i)&b))ans^=(1<<i);
			int L=max(ans-x,0),R=ans+((1<<i)-1)-x;
			if(R<0||!query(0,maxm,rt[l],rt[r],L,R))ans^=(1<<i);
		}
		printf(
	}
	return 0;
}