36| 选数异或

一、核心思路

        本题可以利用预处理以及异或的性质来解决。

        对于当前数字，只要前面出现过 ，那这两个数就能组成答案

• 预处理：遍历数组，记录每个位置 i 之前，最近一次出现 的位置
• 下标最大值：用 记录1~i 中，所有满足条件的最近数对的下标最大值
• 查询：只要 ，说明区间  内一定有解

二、代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5 + 10;
int n, m, x, l, r;
int a[N], f[N]; // f[i] = 1~i 中最靠右的有效配对位置
unordered_map <int, int> lst; // 统计每个数字最后出现的位置
signed main()
{
cin >> n >> m >> x;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
lst[a[i]] = i;
f[i] = max(f[i-1], lst[a[i] ^ x]);
}
while(m–)
{
cin >> l >> r;
if(f[r] >= l) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}