【题解 && 线段树】[蓝桥杯 2022 省 A] 选数异或

题目描述：

[蓝桥杯 2022 省 A] 选数异或

题目描述

给定一个长度为 $n$ 的数列 $A_1,A_2,\cdots ,A_n$ 和一个非负整数 $x$, 给定 $m$ 次查询, 每次询问能否从某个区间 $[l,r]$ 中选择两个数使得他们的异或等于 $x$ 。

输入格式

输入的第一行包含三个整数 $n,m,x$ 。

第二行包含 $n$ 个整数 $A_1,A_2,\cdots ,A_n$。

接下来 $m$ 行，每行包含两个整数 $l_i,r_i$ 表示询问区间 $\left[l_i,r_i\right]$ 。

输出格式

对于每个询问, 如果该区间内存在两个数的异或为 $x$ 则输出 yes, 否则输出 no。

样例 #1

样例输入 #1

4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
1
2
3
4
5
6

样例输出 #1

yes
no
yes
no
1
2
3
4

提示

【样例说明】

显然整个数列中只有 2,3 的异或为 1 。

【评测用例规模与约定】

对于 $20\%$ 的评测用例, $1\le n,m\le 100$;

对于 $40\%$ 的评测用例, $1\le n,m\le 1000$;

对于所有评测用例, $1\le n,m\le 10^5,0\le x<2^{20},1\le l_i\le r_i\le n$ ， $0\le A_i<2^{20}$ 。

蓝桥杯 2022 省赛 A 组 D 题。

---

分析：

对于异或，我们有如下性质：
$$axorb=c->axorc=b$$

于是问题就转化成：
$\exists i\in [l,r],\exists j\in [l,r]$，有$a[j]=a[i]xorx$

对于每一个$i$，我们如何寻找合法的$j$呢？
对于一个$i$，如果他有若干个合法的j，我们显然只要找到最近的那个j就可以了。
我们用一个数组$La[i]$表示数字$i$上次出现的位置
那么对于位置$i$，他最近的一个j的位置就是$La[a[i]xorx]$

这样我们就找到了每个数字最近的合法数字的位置。

那么对于一个区间$[l,r]$，我们如何进行求解呢？
由于题目中的问题是问我们是否存在这样一对数字满足条件
也就是说这是一个存在性问题，只要存在一对合法的数字即可
就是说:
$\exists i\in [l,r],有La[i]>=l$

因此我们只需要对区间$[l,r]$之间所有的$La[i]$求一个最大值即可
线段树可以维护

---

Code

#include
using namespace std;

const int N = 1e5+10;
map < int , int > Now,La;
int n,m,k;

struct Tr{
	int tr[4*N];
	void Insert(int x,int l,int r,int po,int v){
		if (l == r){
			tr[x] = v; return;
		}
		int Mid = (l+r)>>1;
		if (po <= Mid) Insert(x<<1,l,Mid,po,v);
		else Insert(x<<1|1,Mid+1,r,po,v);
		tr[x] = max(tr[x<<1],tr[x<<1|1]);
		return ;
	}
	int Ask(int x,int l,int r,int L,int R){
		if (L <= l && r <= R) return tr[x];
		int Mid = l+r>>1;
		int Max = 0;
		if (L <= Mid) Max = max(Max,Ask(x<<1,l,Mid,L,R));
		if (R > Mid) Max = max(Max,Ask(x<<1|1,Mid+1,r,L,R));
		return Max;
	}
}tr;

int a[N];

int main(){
	scanf("%d %d %d",&n,&m,&k);
	for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
	for (int i = 1; i <= n; i++){
		int x = 0;
		if (Now.count(a[i]^k)) x = Now[a[i]^k];
		Now[a[i]] = i;
		tr.Insert(1,1,n,i,x);
	}
	for (int i = 1; i <= m; i++){
		int l,r; scanf("%d %d",&l,&r);
		int Max = tr.Ask(1,1,n,l,r);
		if (Max >= l) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48