题意

给定一个长度为 $n$ 的序列 $a\{n\}$，有 $m$ 次询问，每次查询 $\max_{l \le i \le r} (a_i + x) \oplus b$ 的值。

$1 \le n \le 2 \times 10^5,0 \le a,b,x \le 10^5.$

分析

这个思路比较新奇。首先考虑是求异或最大值，大概率要带一个 $\log a_i$ 的时间复杂度去枚举每一位。假设我们从高到低枚举到了 $p$ 这一位，按照正常思路我们要判断在 $[l,r]$ 范围内是否存在 $a_i$，使得 $p + 1$ 位与 $b$ 的 $p + 1$ 位不同。但是这一题我们要判断的是 $a_i + x$ 的 $p + 1$ 位与 $b$ 的 $p + 1$ 不同，这个不好处理，我们考虑转化为范围来处理。

我们假设现在选择的值为 $ans$（注意是值，不是答案，且这个值只保留最高的 $p$ 位），不妨设 $b$ 的这一位是 $1$，那么 $a_i + x$ 的范围就是 $a_i + x \in [ans,ans+2^p)$，而我们就可以得到 $a_i \in [ans-x,ans+2^p-x)$，我们就要判断是否 $\exists i \in [l,r],a_i \in [ans-x,ans+2^p-x)$。这个问题我们可以考虑使用主席树（可持久化线段树）来解决，具体实现就是板子。$b$ 这一位是 $0$ 同理，范围变成 $[ans+2^p-x,ans+2^{p+1}-x)$ 即可。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define N 200005
#define V 100000
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, a[N], b, x, l, r;
int tr[N << 5], ls[N << 5], rs[N << 5], rt[N], ep;
void add(int &p, int t, int l, int r, int x, int k){
    if (!p) p = ++ep;
    tr[p] = tr[t] + k;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (x <= mid) add(ls[p], ls[t], l, mid, x, k), rs[p] = rs[t];
    else add(rs[p], rs[t], mid + 1, r, x, k), ls[p] = ls[t];
}
int ask(int a, int b, int l, int r, int nl, int nr){
    if (nl <= l && r <= nr) return tr[a] - tr[b];
    int mid = (l + r) >> 1, ans = 0;
    if (nl <= mid) ans += ask(ls[a], ls[b], l, mid, nl, nr);
    if (nr > mid) ans += ask(rs[a], rs[b], mid + 1, r, nl, nr);
    return ans;
}
int main(){
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++) a[i] = rd(), add(rt[i], rt[i - 1], 0, V, a[i], 1);
    while (m--){
        b = rd(), x = rd(), l = rd(), r = rd();
        int ans = 0;
        for (int i = 30; i >= 0; i--){
            int c = (((b >> i) & 1) ^ 1), kl = max(ans + (c << i) - x, 0), kr = min(ans + (c << i) + (1 << i) - 1 - x, V);
            if (kl <= kr && ask(rt[r], rt[l - 1], 0, V, kl, kr) > 0) ans |= (c << i);
            else ans |= ((c ^ 1) << i);
        }printf ("%d\n", ans ^ b);
    }
    return 0;
}