最大异或队 暂存
作者:
Molip
,
2023-07-30 21:45:55
,
所有人可见
,
阅读 85
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int son[N][2], cnt[N], idx;
int n;
int a[N];
vector<int> get2(int x){
vector<int> a;
while(x){
a.push_back(x & 1);
x >>= 1;
}
reverse(a.begin(), a.end());
return a;
}
void insert(int x){
auto a = get2(x);
int p = 0;
for(int i = 0; i < a.size(); ++ i){
int u = a[i];
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] = x;
}
int query(int x){
auto a = get2(x);
int p = 0;
for(int i = 0; i < a.size(); ++ i){
int u = a[i];
if(u == 0) p = son[p][u + 1] ? son[p][u + 1] : son[p][u];
if(u == 1) p = son[p][u - 1] ? son[p][u - 1] : son[p][u];
}
return cnt[p];
}
int main(){
cin >> n;
int ans = 0;
for(int i = 1; i <= n; ++ i){
cin >> a[i];
insert(a[i]);
}
for(int i = 1; i <= n; ++ i){
ans = max(ans, a[i] ^ query(a[i]));
}
cout << ans;
return 0;
}
int query(int x){ auto a = get2(x); int p = 0; for(int i = 0; i < a.size(); ++ i){ int u = a[i]; // u = 0 or u = 1 int v = 1 - u; // v = 1 if u = 0, v = 0 if u = 1 if(son[p][v]) { p = son[p][v]; } else { p = son[p][u]; } } return cnt[p]; }