7327: CodeChef SUBARRAYREM - Subarray Removal
[Creator : ]
Description
Chef has a binary array $A$ of length $N$. In one operation, Chef does the following:
1. Select any $L$ and $R$ such that $(1 \le L \lt R \le |A|)(1≤L<R≤∣A∣)$
2. Add $A_L \oplus A_{L+1} \oplus \ldots \oplus A_R$ to his score. Here, $\oplus$ denotes the bitwise XOR operation.
3. Remove the subarray $A_{L \dots R}$ from A
Determine the maximum score Chef can get after performing the above operation any number of times.
1. Select any $L$ and $R$ such that $(1 \le L \lt R \le |A|)(1≤L<R≤∣A∣)$
2. Add $A_L \oplus A_{L+1} \oplus \ldots \oplus A_R$ to his score. Here, $\oplus$ denotes the bitwise XOR operation.
3. Remove the subarray $A_{L \dots R}$ from A
Determine the maximum score Chef can get after performing the above operation any number of times.
Input
The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
The first line of each test case contains an integer $N$ — the size of the array A.
The second line of each test case contains $N$ space-separated integers $A_1, A_2, \dots, A_N$ denoting the array A.
The first line of each test case contains an integer $N$ — the size of the array A.
The second line of each test case contains $N$ space-separated integers $A_1, A_2, \dots, A_N$ denoting the array A.
Output
For each test case, output the maximum score Chef can get.
Constraints
$1≤T≤10^5$
$1 \leq N \leq 10^5$
$A_i \in \{0, 1\}$
The sum of N over all test cases won't exceed $2 \cdot 10^5$.
$1 \leq N \leq 10^5$
$A_i \in \{0, 1\}$
The sum of N over all test cases won't exceed $2 \cdot 10^5$.
Sample 1 Input
3
5
1 0 0 0 1
3
1 1 1
3
0 0 0
Sample 1 Output
2
1
0
Test Case 1: We can perform the following moves:
Test Case 2: We can perform the following move:
- A = [1, 0, 0, 0, 1]. Select L = 1 and R = 3 and remove subarray [1, 0, 0]. A becomes [0, 1].
- A = [0, 1]. Select L = 1 and R = 2 and remove subarray [0, 1]. AA becomes [].
Test Case 2: We can perform the following move:
- A = [1, 1, 1]. Select L = 1 and R = 3 and remove subarray [1, 1, 1]. A becomes [].