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

竟然没有题解，那么本蒟蒻就随手写一个......

首先有一个很常见的结论： 如果 $a \otimes b=x$ 那么 $a \otimes x=b$ 。

根据这个结论，我们可以对 $A$ 数列中每一项异或上一个数 $x$ 得到 $B$ 数列。即： b[i]=a[i]^x; 。

然后题意就转化为：给定一个区间 $[l,r]$ ，问数组 $a$ 和数组 $b$ 在这个区间内是否有相同的数。

这个问题看起来很简单，应该有非常简单又巧妙的解法。但是本蒟蒻一眼就想拿莫队来做，是目前的最劣解。

先离散化，再开两个桶，每次移动指针的时候判断是否影响答案。

时间复杂度：$O(n \log n+n\sqrt{n})$ （不知道对不对）。

代码：

cpp
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
49
50
51
52
53
54
#include<iostream>
#include<algorithm>
#include<cmath> 
#define int long long
#define _ 100005
using namespace std;

int blo,bl[_],a[_],b[_],uni[_<<1],tot,n,m,x;
struct Query{int l,r,id,ans;} q[_];

//注意开两倍数组 
int l=1,r,ans,bu1[_<<1],bu2[_<<1];
inline void add(int x){
	bool st=((bu1[a[x]]>0&&bu2[a[x]]>0)||(bu1[b[x]]>0&&bu2[b[x]]));
	bu1[a[x]]++;
	bu2[b[x]]++;
	bool ed=((bu1[a[x]]>0&&bu2[a[x]]>0)||(bu1[b[x]]>0&&bu2[b[x]]));
	if(!st&&ed) ans++;//判断是否对答案产生影响 
}
inline void del(int x){
	bool st=((bu1[a[x]]>0&&bu2[a[x]]>0)||(bu1[b[x]]>0&&bu2[b[x]]));
	bu1[a[x]]--;
	bu2[b[x]]--;
	bool ed=((bu1[a[x]]>0&&bu2[a[x]]>0)||(bu1[b[x]]>0&&bu2[b[x]]));
	if(st&&!ed) ans--;
}

signed main(){
	ios::sync_with_stdio(false);
	//读入数据 
	cin>>n>>m>>x;
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i]^x,uni[++tot]=a[i],uni[++tot]=b[i];
	for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
	//离散化 
	sort(uni+1,uni+tot+1);
	tot=unique(uni+1,uni+tot+1)-uni-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(uni+1,uni+tot+1,a[i])-uni,b[i]=lower_bound(uni+1,uni+tot+1,b[i])-uni;
	//分块 
	blo=sqrt(n);
	for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1;
	sort(q+1,q+m+1,[](Query qa,Query qb){return bl[qa.l]==bl[qb.l]? qa.r<qb.r:qa.l<qb.l;});
	//处理询问 
	for(int i=1;i<=m;i++){
		while(l<q[i].l) del(l++);
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(r>q[i].r) del(r--);
		q[i].ans=ans;
	}
	//输出答案 
	sort(q+1,q+m+1,[](Query qa,Query qb){return qa.id<qb.id;});
	for(int i=1;i<=m;i++) cout<<(q[i].ans? "yes":"no")<<endl;
	return 0;
}