Pagini recente » Cod sursa (job #2230585) | Cod sursa (job #2856176) | Cod sursa (job #2493747) | Cod sursa (job #410433) | Cod sursa (job #3354276)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int NMAX = 1e5 + 5;
int spx[NMAX];
struct Trie{
int idx;
Trie* bits[2];
Trie(){
idx = 0;
bits[0] = bits[1] = nullptr;
}
};
void insert( Trie* root, int x, int idx ){
Trie *curr = root;
for( int i = 20; i >= 0; i-- ){
int bit = ( x >> i) & 1 ;
if( curr->bits[bit] == nullptr )
curr -> bits[bit] = new Trie();
curr = curr->bits[bit];
}
curr->idx = idx;
}
int query( Trie* root, int x) {
Trie *curr = root;
for( int i = 20; i>= 0; i-- ){
int bit = ( x >> i) & 1 ;
if( curr->bits[!bit] != nullptr )
curr = curr->bits[!bit];
else{
if( curr->bits[bit] != nullptr )
curr = curr->bits[bit];
else
return curr->idx;
}
}
return curr->idx;
}
int main(){
int n, x;
fin >> n;
Trie* root = new Trie();
insert(root, 0, 0);
int maxXor = 0, l, r;
for( int i = 1; i <= n; i++ ){
fin >> x;
spx[i] ^= spx[x-1] ^ x;
int k = query(root, spx[i]);
if( maxXor < (spx[k] ^ spx[i]) ){
maxXor = spx[k] ^ spx[i];
l = k+1;
r = i;
}
insert(root, spx[i], i);
}
fout << maxXor << ' ' << l << " " << r << "\n";
return 0;
}