第十三届蓝桥杯省赛A组题解传送门

题目大意

给定一个数组$a$以及$m$个询问
每次询问$[l,r]$间是否存在$i,j$满足$a[i]\bigoplus a[j]=x$

解题思路

处理出$c$数组，$c[i]$存储$a[i]$右边第一个满足$a[i]\bigoplus a[j]=x$的$a[j]$下标$j$
对$c$数组建线段树维护区间最小值
只要$[l,r]$的$min(c[i])\leq r$就说明$yes$

具体代码

#include <bits/stdc++.h>
const int N = 1e5 + 10;
int n, m, x;
int a[N];
int c[N]; //存储a[i]右边第一个满足a[i]^a[j]=x的a[j]下标j
struct node
{
    int minv;
} tr[N * 4];
node operator+(const node &l, const node &r)
{
    return {std::min(l.minv, r.minv)};
}
void pushup(int id)
{
    tr[id] = tr[id * 2] + tr[id * 2 + 1];
}
void build(int id, int l, int r)
{
    if (l == r)
        tr[id].minv = c[l];
    else
    {
        int mid = l + r >> 1;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        pushup(id);
    }
}
int query(int id, int l, int r, int ql, int qr)
{
    if (l == ql && r == qr)
        return tr[id].minv;
    int mid = l + r >> 1;
    if (qr <= mid)
        return query(id * 2, l, mid, ql, qr);
    else if (ql > mid)
        return query(id * 2 + 1, mid + 1, r, ql, qr);
    else
        return std::min(query(id * 2, l, mid, ql, mid), query(id * 2 + 1, mid + 1, r, mid + 1, qr));
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    std::cin >> n >> m >> x;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> a[i];
        c[i] = N;
    }
    std::map<int, int> S;
    for (int i = n; i >= 1; --i)
    {
        if (S.count(a[i] ^ x))
            c[i] = S[a[i] ^ x];
        S[a[i]] = i;
    }
    /*
    for (int i = 1; i <= n; ++i)
        std::cout << c[i] << ' ';
    */
    build(1, 1, n); //对c[i]建立维护区间最小值的线段树
    while (m--)
    {
        int l, r;
        std::cin >> l >> r;
        if (query(1, 1, n, l, r) <= r)
            std::cout << "yes" << '\n';
        else
            std::cout << "no" << '\n';
    }
    return 0;
}