Untitled
unknown
plain_text
2 years ago
1.9 kB
6
Indexable
#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; } }; void keep(int n ){ int temp = 0; for(int i=0;i<300;i++) temp++ ; int arr[n]; for(int i=0;i<n ;i++){ arr[i]=5; } return ; } 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]; keep(20); int ans=maxSubarrayXOR(n,arr); cout<<ans<<endl; } }
Editor is loading...