AcWing 4645. 选数异或【python3】
原题链接
中等
作者:
dflying
,
2024-02-20 09:55:05
,
所有人可见
,
阅读 34
# 这个题目真的很妙,首先你要知道 A^B=C 那么有 B^C=A 这个是异或的题目你需要知道的规律
# 然后这个题目比较难的是 如何化零为整,开始我的想法就是 记录从0~j 异或对的个数,后面是以区间的形式查询,那么
# 你不知道做出贡献的异或对的区间,因此这个题目化零为整的思想就很妙了,它记录的是 离r最近的异或对的左端点索引
# 那么区间是否有异或对就很好好判断了,直接看离r最近的异或对的左端点是否在l后面就可以啦
# 是不是很妙呢?
n,m,x=map(int,input().split())
A=list(map(int,input().split()))
max_num=2**20+10
distance=[0 for i in range(max_num)]
dp=[0 for i in range(n+1)]
for i in range(n):
y=A[i]^x
dp[i+1]=max(dp[i],distance[y])
distance[A[i]]=i+1 #不断遍历的因此记录下来的一定是离i最近的哦
while m:
l,r=map(int,input().split())
print("no" if dp[r]<l else "yes")
m-=1