思路:首先可以忽略[l,r]的限制,先预处理出来所有异或等于x的点对
然后对所有的点对按first排序设该序列为S
然后对于每个询问[l,r],首先在S中找到第一个大于等于l的点对设为a,a后面都是满足点对的左端点被包括的
再来考虑右端点r只需要在a->最后中存在点对的右端点小于r就可以了因此可以在刚才同时预处理一个从右往左所有点对的最小值
然后逐个处理就可以了
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
int n,m,x;
int a[N];
int tr[N*21][2],idx,cnt;
vector<int> mem[N*21];
PII b[N];
int c[N],minv[N];
void insert(int x,int y){
int p=0;
for(int i=20;i>=0;i--){
int t=x>>i&1;
if(!tr[p][t]) tr[p][t]=++idx;
p=tr[p][t];
}
mem[p].push_back(y);
}
void find(int x,int y){
int p=0;
for(int i=20;i>=0;i--){
int t=x>>i&1;
if(!tr[p][t]) return ;
p=tr[p][t];
}
for(int t:mem[p]) b[cnt++]={t,y};
}
int main(void){
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
find(x^a[i],i);
insert(a[i],i);
}
memset(minv,0x3f,sizeof minv);
sort(b,b+cnt);
for(int i=cnt-1;i>=0;i--) minv[i]=min(minv[i+1],b[i].second),c[i]=b[i].first;
c[cnt]=N;
int l,r;
while(m--){
scanf("%d%d",&l,&r);
if(l==r){
printf("no\n");
continue;
}
int t=lower_bound(c,c+cnt+1,l)-c;
if(minv[t]<=r) printf("yes\n");
else printf("no\n");
}
return 0;
}