D1

我们先来看D1啊 我最开始理解的就是一个翻转 但是只在0开始时才是正确的
这里就有一组hack 1 2
0 3
他会输出0 而不是3 为啥？？？ 这样一想好像是正确的 每次要是01数字不同了这一位就是1 要是不一样的话可记可不记
但是这是对于从0到r 来说 因为我们的r每次不记录 都有一个类似与互补的数来帮他 而l不为0之后就没有了
就比如说一个0到x的一个数组 你xor任何数他都是连续的 而l不等于0之后 就会有间断的
code：

#include <bits/stdc++.h>
using namespace std;
const int N =5e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
const int MAXN = 5e5 + 5;
int son[MAXN*30][2], idx;
int MAXBIT = 20,val[MAXN];
void init(){
    son[0][0] = son[0][1] = 0;
    idx = 1;
}
void add(int n){
    int p = 0;
    for (int i = MAXBIT; i >= 0; --i)
    {
        int u = (n >> i) & 1;
        if (!son[p][u]) {
            son[idx][0] = son[idx][1] = 0;
            son[p][u] = idx++;
        }
        p = son[p][u];
    }
    val[p] = n;
}
int query_min(int x){
    int p=0;
    for(int i=MAXBIT;i>=0;i--){
        int u=x>>i&1;
        if(son[p][u])p=son[p][u];
        else p=son[p][u^1];
    }
    return val[p]^x;
}
int query_max(int x){
    int p=0;
    for(int i=MAXBIT;i>=0;i--){
        int u=x>>i&1;
        if(son[p][u^1])p=son[p][u^1];
        else p=son[p][u];
    }
    return val[p]^x;
}
void solve() {
    init();
    int l,r;cin>>l>>r;
    int n=r-l+1;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        add(a[i]);
    }
    for(int i=0;i<n;i++){
        int x=a[i]^l;
        if(query_min(x)==l&&query_max(x)==r){
            cout<<x<<endl;
            break;
        }
    }
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

D2

然后我们来看D2 要是没了如上性质 我们该如何做
我们考虑把a[i] 插入 建立一颗01trie
然后枚举x跑一边最大值最小值是否为l r即可
为啥这样就对了
因为不同数xor同一个数 结果都是不同的 可以考虑有一位不同 不管x为啥 他们最后都是不同的
又因为a[i]不同 a[i]再xor x 一遍 也是不同的
可是这样是n^2的
然后我们看到了数组长度不超过2^17 那我们变形一下即可 -> a[i] xor x = l 两边xor x xor l -> a[i] xor l = x ;
那我们枚举a[i]即可

#include <bits/stdc++.h>
using namespace std;
const int N =5e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
const int MAXN = 5e5 + 5;
int son[MAXN*30][2], idx;
int MAXBIT = 20,val[MAXN];
void init(){
    son[0][0] = son[0][1] = 0;
    idx = 1;
}
void add(int n){
    int p = 0;
    for (int i = MAXBIT; i >= 0; --i)
    {
        int u = (n >> i) & 1;
        if (!son[p][u]) {
            son[idx][0] = son[idx][1] = 0;
            son[p][u] = idx++;
        }
        p = son[p][u];
    }
    val[p] = n;
}
int query_min(int x){
    int p=0;
    for(int i=MAXBIT;i>=0;i--){
        int u=x>>i&1;
        if(son[p][u])p=son[p][u];
        else p=son[p][u^1];
    }
    return val[p]^x;
}
int query_max(int x){
    int p=0;
    for(int i=MAXBIT;i>=0;i--){
        int u=x>>i&1;
        if(son[p][u^1])p=son[p][u^1];
        else p=son[p][u];
    }
    return val[p]^x;
}
void solve() {
    init();
    int l,r;cin>>l>>r;
    int n=r-l+1;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        add(a[i]);
    }
    for(int i=0;i<n;i++){
        int x=a[i]^l;
        if(query_min(x)==l&&query_max(x)==r){
            cout<<x<<endl;
            break;
        }
    }
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}