4645. 选数异或
给定一个长度为 nn 的数列 A1,A2,⋅⋅⋅,AnA1,A2,···,An 和一个非负整数 xx，给定 mm 次查询，每次询问能否从某个区间 [l,r][l,r] 中选择两个数使得他们的异或等于 xx。
输入格式
输入的第一行包含三个整数 n,m,xn,m,x。
第二行包含 nn 个整数 A1,A2,⋅⋅⋅,AnA1,A2,···,An。
接下来 mm 行，每行包含两个整数 li,rili,ri 表示询问区间 [li,ri][li,ri]。
输出格式
对于每个询问，如果该区间内存在两个数的异或为 xx 则输出 yes，否则输出 no。
数据范围
对于 20%20% 的评测用例，1≤n,m≤1001≤n,m≤100；
对于 40%40% 的评测用例，1≤n,m≤10001≤n,m≤1000；
对于所有评测用例，1≤n,m≤1000001≤n,m≤100000，0≤x<2200≤x<220，1≤li≤ri≤n1≤li≤ri≤n，0≤Ai<2200≤Ai<220。
输入样例：
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
输出样例：
yes
no
yes
no
样例解释
显然整个数列中只有 2,32,3 的异或为 11。
n,m,x = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
'''
如果a^b=x，记ab为满足条件一个数对
根据异或运算交换律，a^b=x ==> a^x=b,所以遇到一个数字a时，
我们可以知道与它能组成数对的数是谁
我们可以在遍历数组时，维护一个哈希表，记录每个数字最后出现的位置，然后从哈希表中
找能与当前数字组成数对的数。
如果能找到的话，记录下与与当前数字组成数对的数的最大位置mx;不能，则赋值为0
这样我们就得到了，能个a[i]组成数对的那个数的最大位置了
根据这个信息，可以维护前i个数字能和a[i]组成数对的那个数的最大位置，记为dp[i]
而且，dp[i]=max(dp[i-1],last[a[i]^x)，记a[i]的满足条件的数为
能和a[i]组成数对的数的最大位置。这个公式的意思是，
前i个数中满足条件的数的最大位置 = max(前i-1个数中满足条件的数的最大位置,
第i个满足条件的数的最大位置)
比如 1 2 3 4 x=1
对于1 由于1^1=0，说明能和1组成数对的数是0，然后从last中找0最后出现位置，发现没有
所以，dp[1]=0
对于2 由于2^1=3，说民能和2组成数对的数是3，然后去last中找它最后出现的位置，发现也没有
故dp[2] = max(dp[1],last[3])=0
对于3 由于3^1=2，说明能和3组成数对的数是2，然后去last中找它最后出现的位置，
发现last[2]=2,故dp[3] = max(dp[2],last[2])=2
对于4 由于4^1=5，说明能和4组成数对的数是5，然后去last中找它最后出现的位置，发现没有
发现last[2]=2,故dp[4] = max(dp[3],last[5])=2
然后，如何检查区间[l,r]中有没有符合条件的数对呢?
因为dp[r]代表，前r个数中符合条件的数对的最大位置是多少，所以只要dp[r]>=l，就说明
满足条件的数在[l,r]区间了
'''
last = {}
# dp[i]前i个数中能和k组成数对的最大下标
dp = [0]*(n+1)
for i in range(1,n+1):
# 记录每个数最后一次出现的位置
last[a[i-1]]=i
# 能和第i个数组成数对的数是k
k = x^a[i-1]
dp[i]=max(dp[i-1],last[k] if k in last else 0)
print(dp)
while m:
l,r = [int(x) for x in input().split()]
print('yes' if dp[r]>=l else 'no')
m-=1