1. 2024: [蓝桥杯2022初赛] 选数异或
传送门:http://oj.ecustacm.cn/problem.php?id=2024
1.1. 题意
给定数组和整数,次询问,每次询问区间是否存在两个数字使得异或值等于。
1.2. Tag
线段树、表
1.3. 难度
☆☆☆
1.4. 思路
由于给定,对于区间中的每个数字而言,只需要判断区间中是否存在。
暴力判断会超时,如何快速判断区间而不是一个一个来判断?
对每个数字,找到它左边最近的,满足,则二元组是一个合法解,其中。
为什么一定是左边最近合法位置而不是右边最近?
二者是一样的,因为i找到的左边最近合法位置是,找到的右边最近是。
对于每个,都找到左边最近合法的,记为,满足。
那么对于询问中是否存在两个数字异或值等于,等价于询问中是否存在一个满足:。
存在一个即可满足条件,相当于最大的大于即可,即。
问题转换成:求区间最大值问题,使用线段树或者表即可。
那如何快速得到数组?从左往右遍历时,利用记录数字上一次出现的位置,那么。
注:本题也可使用莫队算法维护区间异或等于的次数来求解。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
int tree[maxn << 2];
int Left[maxn], pos[(1 << 20) + 10];
int a[maxn], n, m, x;
//线段树模板
void build(int o, int l, int r){
if(l == r)
{
tree[o] = Left[l];
return;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid);
build(o << 1 | 1, mid + 1, r);
tree[o] = max(tree[o << 1], tree[o << 1 | 1]);
}
int query(int o, int l, int r, int L, int R){
if(L <= l && r <= R)return tree[o];
int mid = (l + r) >> 1;
int ans = 0;
if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));
if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));
return ans;
}
int main(){
scanf("%d%d%d", &n, &m, &x);
for(int i = 1; i <= n; i++) //预处理Left数组
{
scanf("%d", &a[i]);
Left[i] = pos[a[i] ^ x];
pos[a[i]] = i;
}
build(1, 1, n);//线段树建树
while(m--)
{
int l, r;
scanf("%d%d", &l, &r);
if(query(1, 1, n, l, r) >= l)//查询区间最值
printf("yes\n");
else
printf("no\n");
}
return 0;
}