【题解 线段树】[蓝桥杯 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

yes
no
yes
no

提示

【样例说明】

显然整个数列中只有 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<bits/stdc++.h>
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;
}