Guest User

Untitled

a guest
Aug 25th, 2017
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.45 KB | None | 0 0
  1. import java.io.IOException;
  2. import java.util.Scanner;
  3.  
  4. /**
  5.  * Created by arpit on 15/12/16.
  6.  */
  7. class MaxXorSubArray {
  8.  
  9.     static int a[]=new int[100000];
  10.  
  11.  
  12.     public static void main(String[] args) throws IOException {
  13.  
  14.         //BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  15.         Scanner sc=new Scanner(System.in);
  16.         int t,n;
  17.         String[]s;
  18.         t=sc.nextInt();
  19.         while (t-->0){
  20.             n=sc.nextInt();
  21.             //s=br.readLine().split("\\s");
  22.             for (int i = 0; i < n; i++) {
  23.                 a[i]=sc.nextInt();
  24.                 //a[i]=Integer.parseInt(s[i]);
  25.             }
  26.             System.out.println(solve(n));
  27.         }
  28.  
  29.     }
  30.  
  31.     private static int solve(int n) {
  32.         Trie trie=new Trie();
  33.         int pre=0,ans=0;
  34.         trie.insert(0);
  35.         for (int i = 0; i < n; i++) {
  36.             pre^=a[i];
  37.             System.out.println(trie.query(pre));
  38.             ans=Integer.max(trie.query(pre),ans);
  39.             trie.insert(pre);
  40.         }
  41.         return ans;
  42.     }
  43.  
  44.     static class Trie{
  45.  
  46.         TrieNode root;
  47.  
  48.         public Trie() {
  49.             root=new TrieNode();
  50.         }
  51.  
  52.         class TrieNode{
  53.             int val;
  54.             TrieNode[]child;
  55.  
  56.             public TrieNode() {
  57.                 child=new TrieNode[2];
  58.             }
  59.         }
  60.  
  61.         int query(int key){
  62.  
  63.             TrieNode temp=root;
  64.             for (int i = 31; i>=0; i--) {
  65.                 int currbit;
  66.  
  67.                 if ( (key&(1<<i) )>=1)currbit=1;
  68.  
  69.                 else currbit=0;
  70.  
  71.                 if (temp.child[1-currbit]!=null){
  72.                     temp=temp.child[1-currbit];
  73.                     //System.out.println(temp);
  74.                 }
  75.  
  76.                 else if (temp.child[currbit]!=null){
  77.                     temp=temp.child[currbit];
  78.                 }
  79.             }
  80.             return temp.val^key;
  81.         }
  82.  
  83.         void insert(int key){
  84.  
  85.             TrieNode temp=root;
  86.             for (int i = 31; i>=0 ; i--) {
  87.                 int currBit;
  88.  
  89.                 if ((key&(1<<i))>=1) currBit = 1;
  90.  
  91.                 else currBit=0;
  92.  
  93.                 if (temp.child[currBit]==null){
  94.                     temp.child[currBit]=new TrieNode();
  95.                     temp=temp.child[currBit];
  96.                 }
  97.  
  98.                 else
  99.                     temp=temp.child[currBit];
  100.             }
  101.             temp.val=key;
  102.  
  103.         }
  104.     }
  105.  
  106. }
Add Comment
Please, Sign In to add comment