Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.7 kB
1
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

struct Node{
    Node* links[2];
    bool isPresent(int bit){
        return (links[bit]!=NULL);
    }
    void insertInLinks(int bit){
        links[bit]=new Node();
    }
    Node* getReferenceNode(int bit){
        return links[bit];
    }
};
class Trie{
    private: Node* root;
    public:
    Trie(){
        root=new Node();
    }
    void insert(int num){
        Node* node=root;
        for(int i=31;i>=0;i--){
            int bit=(num>>i)&1;
            if(node->isPresent(bit)==false){
                node->insertInLinks(bit);
            }
            node=node->getReferenceNode(bit);
        }
    }
    int maxXor(int num){
        Node* node=root;
        int maxi=0;
        for(int i=31;i>=0;i--){
            int bit=(num>>i)&1;
            if(node->isPresent(1-bit)){
                maxi|=(1<<i);
                node=node->getReferenceNode(1-bit);
            }
            else node=node->getReferenceNode(bit);
        }
        return maxi;
    }
};


    int maxSubarrayXOR(int N, int arr[]){    
        vector<int> a(N);
        a[0]=arr[0];
        for(int i=1;i<N;i++){
            a[i]=a[i-1] xor arr[i];
        }
        Trie trie;
        trie.insert(0);
        for(int i=0;i<N;i++) trie.insert(a[i]);
        int ans=0;
        for(int i=0;i<N;i++){
            ans=max(ans,trie.maxXor(a[i]));
        }
        return ans;
    }
    
    int main(){
        int t;
        cin>>t;
        while(t--){
            int n;
            cin>>n;
            int arr[n];
            for(int i=0;i<n;i++) cin>>arr[i];
            int ans=maxSubarrayXOR(n,arr);
            cout<<ans<<endl;
        }
    }