通过读题我们可以知道，给我们一个区间，进行m次询问，每次询问一个区间内是否存在一个两个下标不同的数的异或等于x。因为a^b = x 与 a = b^x是等价的，那我们不妨使用一个数组来记录i前最近一个与当前数ai异或x之后的值相同值的位置。若这个值在给定区间的左边时，则表示区间内并没有符合条件的数值存在。
若值在区间内则说明存在值能够满足条件。
即1<i<r，若存在1<last[a^x]<i，则说明存在值满足题目条件。我们还可以使用一个数组s记录最近一个满足条件的下标。若s[r]的值大于等于l则说明最近一个满足条件的值在限定的区间之中。直接看代码可能更加地直观一些。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 100010,M = (1<<20)+10; int n,m,x; int last[M],s[N]; int main() { scanf("%d%d%d",&n,&m,&x); for(int i = 1;i<=n;i++) { int a; scanf("%d",&a); s[i] = max(s[i-1],last[a^x]); last[a] = i; } while(m--) { int l,r; scanf("%d%d",&l,&r); if(s[r]>=l) puts("yes"); else puts("no"); } return 0; }
