1. 2024: [蓝桥杯2022初赛] 选数异或

传送门：http://oj.ecustacm.cn/problem.php?id=2024

1.1. 题意

给定数组$a$和整数$x$，$m$次询问，每次询问区间$[l,r]$是否存在两个数字使得异或值等于$x$。

1.2. Tag：

线段树、$ST$表

1.3. 难度：

☆☆☆

1.4. 思路：

由于给定$x$，对于区间$[l,r]$中的每个数字$a[i]$而言，只需要判断区间$[l,r]$中是否存在$a[i]\oplus x$。

暴力判断会超时，如何快速判断区间$[l,r]$而不是一个一个$a[i]$来判断？

对每个数字$a[i]$，找到它左边最近的$a[j]$，满足$a[i]\oplus a[j]=x$，则$<j,i>$二元组是一个合法解，其中$j<i$。

为什么一定是左边最近合法位置而不是右边最近？

二者是一样的，因为i找到的左边最近合法位置是$j$，$j$找到的右边最近是$i$。

对于每个$i$，都找到左边最近合法的$j$，记为$Left[i]=j$，满足$j<i,a[i]\oplus a[j]=x$。

那么对于询问$[l,r]$中是否存在两个数字异或值等于$x$，等价于询问$[l,r]$中是否存在一个$i$满足：$l\le i \le r,l\le Left[i]$。

存在一个$i$即可满足条件，相当于最大的$Left[i]$大于$l$即可，即$l \le Max\{Left[i]|l\le i \le r\}$。

问题转换成：求区间最大值问题，使用线段树或者$ST$表即可。

那如何快速得到$Left$数组？从左往右遍历时，利用$pos[x]$记录数字$x$上一次出现的位置，那么$Left[i]=pos[a[i]\oplus x]$。

注：本题也可使用莫队算法维护区间异或等于$x$的次数来求解。

#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;
}