P8773 [蓝桥杯 2022 省 A] 选数异或 题解
题目链接
简要思路
题目让我们查询是否有两个数 \(a,b\) 满足 \(a \oplus b = x\)，根据异或的性质，我们可以将上式转换为 \(b = a \oplus x\)，因此对于每一个 \(a_i\)，我们只需查询在 \([l,r]\) 的区间内，是否有一个值为 \(a_i \oplus x\) 的数 \(b\)。
每一次遍历整个区间肯定是会超时的，所以我们考虑优化。
维护两个“数组”：
\(f_i\) 代表到 \(i\) 这个位置，前面满足 \(a \oplus b = x\) 的二元组 \((a,b)\) 中最前面的一个数的位置，没有的默认为 \(0\)（即到 \(i\) 这个位置，前面最少要到那个位置才有二元组）。
\(las_i\) 代表 \(i\) 出现的最后一个位置，没有的话也是默认为 \(0\)。
但是注意到：\(0 \leq x<2^{20},0 \leq A_{i}<2^{20}\)，所以我们的 \(las\) 就要用 map 来维护。
对于 \(f_i\) 的转移，一共分为两种情况：
当当前输入的这个数 \(a\) 不会产生新的满足条件的二元组或产生的位置太靠前时，答案就为 \(f_{i-1}\)，否则答案为 \(las_{a \oplus x}\)（根据异或的性质所得），所以我们只需对这两个数取 max，得到较后的数即可。
考虑查询。
查询就很简单了，对于一个 \(r\)，我们只需查询 \(f_r\) 是否 \(\geq l\) 即可（即查看以 \(r\) 结尾的区间，前面最后出现的满足条件的值的位置是否在 \(l\) 后面，也就是查看 \([l,r]\) 这个区间是否包括符合答案的区间）。
完整代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int MAXN=1e5+5;
int n,m,x,a;
int f[MAXN];//f[i] 以 i 结尾上一个满足条件的值的位置
std::map<int,int> las;//las[i] 上一个值为 i 的位置
signed main(){
std::cin>>n>>m>>x;
for(int i=1;i<=n;i++){
std::cin>>a;
f[i]=std::max(f[i-1],las[a^x]);//维护
las[a]=i;//更新最后出现的位置
}
while(m--){
int l,r;
std::cin>>l>>r;
if(f[r]>=l)std::cout<<"yes\n";
else std::cout<<"no\n";//查询
}
return 0;
}