题目链接
解析
看到异或，想到按位处理，这样 \(a + x\) 得看作是一个整体。对于 \(b\) 的第 \(k\) 位，如果其为 \(1\)，则我们希望 \(a + x\) 的对应位为 \(0\)。如何让 \(a + x\) 的第 \(k\) 位为 \(0\) 呢？考虑到 \(a + x\) 的更高位已经确定，设当前确定出来的那部分为 \(y\)，那么 \(a + x\) 的范围应当为 \([y,y + 2^k)\)。
当然，取不取得到就是另一回事了。由上可得此时 \(a\) 的范围应当是 \([y - x,y + 2 ^ k - x)\)，所以需要判断区间内是否存在这样的 \(a\)，可以用主席树来实现。
\(b\) 的第 \(k\) 位为 \(0\) 的情况同理。
代码
#include <bits/stdc++.h>
#define mid ((1ll * l + r) >> 1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 2e5 + 5,M = (1ll << 31) - 1,L = 19,L2 = 17,mod = 998244353;
int cnt[N * L],rt[N],ls[N * L],rs[N * L],siz,a[N];
void push_up(int p){cnt[p] = cnt[ls[p]] + cnt[rs[p]];
}
void add(int x,int &y,int l,int r,int k){if(!y) y = ++siz;if(l == r){cnt[y] = cnt[x] + 1;return;}if(k <= mid){rs[y] = rs[x];add(ls[x],ls[y],l,mid,k);}else{ls[y] = ls[x];add(rs[x],rs[y],mid + 1,r,k);}push_up(y);
}
int ask(int x,int y,int l,int r,int L,int R){if(l > R || r < L) return 0;if(l >= L && r <= R){return cnt[y] - cnt[x];}return ask(ls[x],ls[y],l,mid,L,R) + ask(rs[x],rs[y],mid + 1,r,L,R);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];add(rt[i - 1],rt[i],0,N - 1,a[i]);}while(m--){int b,x,l,r;cin>>b>>x>>l>>r;int now = 0;for(int i=L;i>=0;i--){int f = b & (1 << i);if(f){int res = ask(rt[r],rt[l - 1],0,N - 1,now - x,now + (1 << i) - 1 - x);if(!res) now |= (1 << i);}else{int res = ask(rt[r],rt[l - 1],0,N - 1,now + (1 << i) - x,now + (1 << i + 1) - 1 - x);if(res) now |= (1 << i);}}cout<<(now ^ b)<<'\n';}return 0;
}