题目描述
这道题已经过多方面的学习之后,收获如下:
先修知识:a ^ b = x,那么 a ^ x = b
判断这个区间内l ~ r有没有满足两个数异或为x,可以转化为x ^ r得到的值是不是在l之后,如果存在则yes反之no
这里的r指的是每次输入值的右端点
F[i] 为 满足1 ~ i之间任意两个数异或为x的最大对数的最小的数的下标,详细请看样例。
我们用哈希表last存储每一位数的下标,如果说新存储的a^x的值存在last中同时比f[i]大,需要更新:
f[i] = max(f[i - 1,last[a ^ x) a为每次输入的值
样例
假设F[i] 同时有下标为2 ^ 3 = x和 4 ^ 5 = x,那么f[i] = 4;
本题样例:只有2和3异或为1
那么 f[1] = 0,f[2] = 0,f[3]和f[4]中存在2和3所以下标为2,则f[3] = f[4] = 2
C++ 代码
需要注意的是在更新last时,如果刚开始就赋值会存在x为0的情况,即任何数异或0都为它本身,如果此时赋值显然不成立
eg:x = 0
last[1] = 1 f[1] = last[1 ^ 0] = 1,此时f[1]有值显然是不可能的。
#include<iostream>
#include<unordered_map>
using namespace std;
const int N = 100010;
int f[N];
int n,m,x;
int main()
{
scanf("%d%d%d",&n,&m,&x);
unordered_map<int,int> last;
for(int i = 1; i <= n; i++)
{
int a;
cin >> a;
f[i] = max(f[i - 1],last[a ^ x]);
last[a] = i;
}
while(m --)
{
int l,r;
cin >> l >> r;
cout << (f[r] >= l ? "yes" : "no") << endl;
}
return 0;
}