Pagini recente » Cod sursa (job #866659) | Cod sursa (job #1340908) | Cod sursa (job #2763072) | Cod sursa (job #461110) | Cod sursa (job #2971876)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int N = 1e5 + 1;
int n, lgmax, l, r;
long long ans;
vector<int> v(N);
vector<long long> x(N);
vector<vector<int>> trie(1, vector<int>(2, -1));
vector<int> pos(N * 30 + 1);
int main(){
fin >> n;
for(int i = 1; i <= n; i++){
fin >> v[i];
x[i] = x[i - 1] ^ v[i];
lgmax = max(lgmax, (int)log2(x[i]) + 1);
}
bitset<30> b(x[1]);
int curr = 0;
for(int i = lgmax - 1; i >= 0; i--){
if(trie[curr][b[i]] == -1){
trie[curr][b[i]] = trie.size();
trie.push_back(vector<int>(2, -1));
}
curr = trie[curr][b[i]];
}
pos[curr] = 1;
for(int i = 2; i <= n; i++){
bitset<30> b(x[i]);
int curr = 0;
for(int j = lgmax - 1; j >= 0; j--){
if(b[j] == 0){
if(trie[curr][1] != -1){
curr = trie[curr][1];
}
else if(trie[curr][0] != -1){
curr = trie[curr][0];
}
}else{
if(trie[curr][0] != -1){
curr = trie[curr][0];
}else if(trie[curr][1] != -1){
curr = trie[curr][1];
}
}
}
ans = max(ans, x[i] ^ x[pos[curr]]);
if(ans < x[i] ^ x[pos[curr]]){
ans = x[i] ^ x[pos[curr]];
l = pos[curr] + 1;
r = i;
}
else if(ans == x[i] ^ x[pos[curr]]){
if(l > pos[curr] + 1){
l = pos[curr] + 1;
}
}
curr = 0;
for(int j = lgmax - 1; j >= 0; j--){
if(trie[curr][b[j]] == -1){
trie[curr][b[j]] = trie.size();
trie.push_back(vector<int>(2, -1));
}
curr = trie[curr][b[j]];
}
if(pos[curr] == 0) pos[curr] = i;
}
fout << ans << " " << l << " " << r;
}