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

results matching ""

    No results matching ""