一段区间里求异或值最大容易想到可持久化字典树，然而要加上一个数，就很难受了。
考虑用权值线段树代替字典树，开一颗底层大小为2^k的权值线段树，i的位置代表i-1，那么在字典树上向下走一层刚好对应权值线段树上向下走一层。
这样直接在线段树上走就可以了。
因为要加上x，查询l~r是否存在相当于查询l-x~r-x是否存在，那么一边在（伪）字典树上走，一边在主席树上查询即可。
时间复杂度为log^2
//Achen #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<vector> #include<queue> #include<ctime> #include<cmath> const int mx=1<<19,N=2e5+7; typedef long long LL; using namespace std; int n,m,a[N],ans; template<typename T> void read(T &x) { char ch=getchar(); x=0; T f=1; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f; } int rt[N],tot,ch[N*30][2],sz[30*N]; #define lc ch[x][0] #define rc ch[x][1] #define mid ((l+r)>>1) void update(int &x,int l,int r,int pos,int last) { x=++tot; lc=ch[last][0]; rc=ch[last][1]; sz[x]=sz[last]+1; if(l==r) return; if(pos<=mid) update(lc,l,mid,pos,ch[last][0]); else update(rc,mid+1,r,pos,ch[last][1]); } int qry(int xl,int xr,int l,int r,int ql,int qr) { if(!xr) return 0; if(l>=ql&&r<=qr) return sz[xr]-sz[xl]; if(ql<=mid) if(qry(ch[xl][0],ch[xr][0],l,mid,ql,qr)) return 1; if(qr>mid) if(qry(ch[xl][1],ch[xr][1],mid+1,r,ql,qr)) return 1; return 0; } void Qry(int xl,int xr,int l,int r,int k,int b,int xx) { while(l!=r) { if(b&(1<<k)) { int ql=max(0,l-xx),qr=max(0,mid-xx); if(qry(xl,xr,1,mx,ql,qr)) { ans|=(1<<k); r=mid; } else l=mid+1; } else { int ql=max(0,mid+1-xx),qr=max(0,r-xx); if(qry(xl,xr,1,mx,ql,qr)) { ans|=(1<<k); l=mid+1; } else r=mid; } k--; } } int main() { read(n); read(m); for(int i=1;i<=n;i++) { read(a[i]); update(rt[i],1,mx,a[i]+1,rt[i-1]); } while(m--) { int x,b,l,r; read(b); read(x); read(l); read(r); ans=0; Qry(rt[l-1],rt[r],1,mx,18,b,x); printf("%d ",ans); } return 0; }