题意
分析
题意是查询一段区间中的异或和的最大值，所以可以想到按位贪心
也就是说，我们枚举当前可能的答案(ans=a[i]+x)的每一位（从高到低），于是我们可以发现，
最终答案(a[i])一定落在：
(large [ans+(1<<i)-x,ans+(1<<(i+1))-1-x]) (quad large (b[i])这一位为(large 0))
(large [ans-x,ans+(1<<i)-1-x]) (quad large (b[i])这一位为(large1))
上面两种情况分别对应(b[i])的当前位为(0)和(1)的情况
当(b[i])为(0)，则当前位为(1)答案更优
当(b[i])为(1)，则当前位为(0)答案更优
所以我们直接查询在两段值域区间内有没有数即可，如果有，那么继续下一位的枚举，当前这一位就变成(1/0)，如果没有，那么当前这一位就变成(0/1)，还是继续下一位，直到结束
此时(ans=a[i]+x)，所以我们直接(ans igoplus b)就是最优的答案
因为要区间查询值域上数的个数，所以我们用值域线段树来维护
但是我们这样干只能记录对于下标区间([1,n])的值域线段树（也就是全局），但是我们这里还要求某一个特定区间([l,r])当中的值域线段树
这就是主席树的经典应用了，静态区间第(k)大的问题中我们就用过值域线段树维护值域，然后用下标的差来维护区间即可
所以我们这里采用主席树来维护值域就行了
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){read(t);read(args...);}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
template <typename T>
inline void print(T x){write(x),putchar(' ');}
#define ll long long
#define ull unsigned long long
#define inc(x,y) (x+y>=MOD?x+y-MOD:x+y)
#define dec(x,y) (x-y<0?x-y+MOD:x-y)
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
const int N=2e5+5,M=1e5+5,MOD=1e9+7;
int n,m,a[N],b[N],root[N],cnt;
struct Segment_Tree{
int sum,ls,rs;
#define sum(x) Tree[x].sum
#define ls(x) Tree[x].ls
#define rs(x) Tree[x].rs
}Tree[N<<5];
void build(int &rt,int l,int r){
rt=++cnt;
if(l==r){sum(rt)=0;return;}
int mid=l+r>>1;
build(ls(rt),l,mid),build(rs(rt),mid+1,r);
return ;
}
void modify(int &rt,int pre,int l,int r,int pos,int v){
rt=++cnt;
if(l==r){sum(rt)=sum(pre)+v;return ;}
int mid=l+r>>1;
ls(rt)=ls(pre),rs(rt)=rs(pre),sum(rt)=sum(pre)+v;
if(pos<=mid) modify(ls(rt),ls(pre),l,mid,pos,v);
else modify(rs(rt),rs(pre),mid+1,r,pos,v);
return ;
}
bool query(int u,int v,int l,int r,int ql,int qr){
if(sum(v)-sum(u)<1) return false;
if(ql<=l&&r<=qr) return true;
int mid=l+r>>1,res=0;
if(ql<=mid) res+=query(ls(u),ls(v),l,mid,ql,qr);
if(qr>mid) res+=query(rs(u),rs(v),mid+1,r,ql,qr);
return res;
}
int main(){
read(n),read(m);build(root[0],0,M);
for(int i=1;i<=n;i++){
read(a[i]);
modify(root[i],root[i-1],0,M,a[i],1);
}
for(int i=1,b,x,l,r;i<=m;i++){
read(b),read(x),read(l),read(r);
int ans=0;
for(int k=17;k>=0;k--){
int L,R,op;
if(b&(1<<k)) L=ans,R=ans+((1<<k)-1),op=0;
else L=ans+(1<<k),R=ans+((1<<(k+1))-1),op=1;
if(!query(root[l-1],root[r],0,M,max(L-x,0),min(R-x,M))) op^=1;
ans+=(op<<k);
}
write(ans^b),putchar('
');
}
system("Pause");
return 0;
}