选数异或 (AcWing 4645)

题目链接: https://www.acwing.com/problem/content/description/4648/

题目描述:

评价: 这道题感觉还是蛮有意思的，难度适中，而且有一定的思维含量，值得反复品味。

思路: 首先我们定义一个数组g[N], 其中的每个元素g[i] 表示在所有 i<j<=n 的j中，满足a[j] ^ a[i] = x的最小的那个j.  这是因为如果存在多个这样的j, 最小的那个j一定是最优的，因为他更加容易被包含在一个区间[l,r] 中. 

假设我们已经得到了上面的数组g, 那么实际上题目的问题就转化为: 每次给定一个查询[l,r] ，询问所有 l=< i <=r 的 i 是否存在一个g[i] <= r. 进一步，我们将这个问题转化为:

询问数组g在区间[l,r] 上的最小值是否小于等于r. 这是一个区间查询问题，且这个问题是满足区间可加性的，可以用线段树解决。

那么只需要考虑数组g 是如何构建的，注意到，若给定a, 满足 a^b=c 的b的取值是唯一的(等式两边异或上a就不难证明)，因此，对于每一个位置i，满足t ^ a[i] =x 的值t是唯一的，我们只需要知道数组中数值 t 出现的全部位置即可； 另一方面，由于数组g的定义，因此需要动态维护每个数值出现的索引(要保证后面的位置不能够使用前面的位置的信息)，因此可以用一个队列(先进先出)来进行维护。

参考代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>
#define ll long long
using namespace std;
const int N=1e5+10;
const int inf=1e9+7;
int n,m,x;
int a[N];
int g[N];
unordered_map<int,int> hashs;
queue<int> q[N];
int cnt=0;

struct node{
	int l;
	int r;
	int minnum;
};
node tree[4*N];
void push_up(int cur){
	tree[cur].minnum=min(tree[cur<<1].minnum,tree[cur<<1|1].minnum);
	return ;
}
void build(int cur,int l,int r){
	tree[cur].l=l;
	tree[cur].r=r;
	if(l==r) {
		tree[cur].minnum=g[l];
		return ;
	}
	int mid=l+r>>1;
	build(cur<<1,l,mid);
	build(cur<<1|1,mid+1,r);
	push_up(cur);
	return ;
}

int gets(int cur,int l,int r){
	if(tree[cur].l>=l&&tree[cur].r<=r){
		return tree[cur].minnum;
	}
	int mid=tree[cur].l+tree[cur].r>>1;
	int res1=inf;
	int res2=inf;
	if(l<=mid) res1=gets(cur<<1,l,r);
	if(r>=mid+1) res2=gets(cur<<1|1,l,r);
	int res=min(res1,res2);
	return res;
}

int main(void){
	
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(hashs[a[i]]==0){
			hashs[a[i]]=++cnt;
		}
		q[hashs[a[i]]].push(i);
	}
	for(int i=1;i<=n;i++){
		int tmp=x^a[i];
		q[hashs[a[i]]].pop();
		if(hashs[tmp]==0) g[i]=n+1;
		else{
			if(q[hashs[tmp]].empty()) g[i]=n+1;
			else 
			g[i]=q[hashs[tmp]].front();
		}
		
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		int res=gets(1,l,r);
		if(res<=r) printf("yes\n");
		else printf("no\n");
	}
	
	return 0;
}