引言

题目链接：https://www.luogu.com.cn/problem/P8773

思路

令 dp[i] 表示以 i 结尾且前 i 个中满足 \(a_j \oplus a_k = x\) 的数对中左侧数最靠近右侧的位置。

假设有 \(a_1 \oplus a_2 = x\) 且 \(a_4 \oplus a_6 = x\)

则 dp[3] = 1, dp[7] = 4

那么给出区间后只需要判断 dp[r] 是否大于 l 即可判断是否满足条件。

代码

#include <bits/stdc++.h>
#define N 100010

int a[N];
std::map<int,int> dp,last;

int main() {
	int n,m,x;
	std::cin >> n >> m >> x;

	for (int i = 1 ; i <= n ; i ++ ) {
		std::cin >> a[i];
		dp[i] = std::max(dp[i-1],last[a[i]^x]);
		last[a[i]] = i;
	}

	while(m -- ) {
		int l,r;
		std::cin >> l >> r;

		if(dp[r] < l) std::cout << "no\n";
		else std::cout << "yes\n";
	}

	return 0;
}