自动搬运

查看原文

来自洛谷，原作者为

	Aurora_Borealis_ 私はあなたと一绪に、无数の星を数えたいです。

搬运于2025-08-24 22:42:20，当前版本为作者最后更新于2023-01-03 19:17:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先根据异或性质可得出：

也就是说，对于已经给出的 $a$ 数组，可以求出每一个 $a_i$ 对应的异或值。

考虑设 $f_i$ 表示当i为右端点时，$[1,i]$ 中所有的合法异或值对中最大的左端点。当询问区间 $[l,r]$ 时，只需检验 $f_r$ 是否在区间内即可。

使用哈希表，复杂度 $O(n+m)$。

upd 2023.1.21:

Q1：

把 lst[a[i]]=i 放到 f[i]=max(f[i-1],lst[a[i]^x]); 上面去，否则就有 hack 如下：1 1 0 1 1 1，应输出 yes 实际输出 no，原因是忽略了可以自己跟自己组

A1:

题面中有原文：

选择两个数使得他们的异或等于 $x$。

这里我默认不能重复取。

upd 2025.7.5:

改正了评论区提到的复杂度错误的问题。

代码：

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
using namespace std;
const int N =100005;
int n,m,x; 
int a[N],f[N];
unordered_map<int, int> lst;
int 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]);
	}
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		if(f[r]<l){
			cout<<"no"<<endl;
		}else{
			cout<<"yes"<<endl;
		}
	}
	return 0;
}