Google笔试题求解

原题如下，求大神解释下这题到底啥意思= =  我看了半天愣是没看懂

Problem

Steven has an array of N non-negative integers. The i-th integer (indexed starting from 0) in the array is A_i.

Steven really likes subintervals of A that are xor-even. Formally, a subinterval of A is a pair of indices (L, R), denoting the elements A_L, A_L+1, ..., A_R-1, A_R. The xor-sum of this subinterval is A_L xor A_L+1 xor ... xor A_R-1 xor A_R, where xor is the bitwise exclusive or.

A subinterval is xor-even if its xor-sum has an even number of set bits in its binary representation.

Steven would like to make Q modifications to the array. The i-th modification changes the P_i-th (indexed from 0) element to V_i. Steven would like to know, what is the size of the xor-even subinterval of A with the most elements after each modification?

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case starts with a line containing two integers N and Q, denoting the number of elements in Steven's array and the number of modifications, respectively.

The second line contains N integers. The i-th of them gives A_i indicating the i-th integer in Steven's array.

Then, Q lines follow, describing the modifications. The i-th line contains P_i and V_i, The i-th modification changes the P_i-th element to V_i. indicating that the i-th modification changes the P_i-th (indexed from 0) element to V_i.

Output

For each test case, output one line containing Case #x: y_1 y_2 ... y_Q, where xis the test case number (starting from 1) and y_i is the number of elements in the largest xor-even subinterval of A after the i-th modification. If there are no xor-even subintervals, then output 0.

Limits

Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ A_i < 1024.
0 ≤ P_i < N.
0 ≤ V_i < 1024.

Test set 1 (Visible)

1 ≤ N ≤ 100.
1 ≤ Q ≤ 100.

Test set 2 (Hidden)

1 ≤ N ≤ 10⁵.
1 ≤ Q ≤ 10⁵.

Sample

2
4 3
10 21 3 7
1 13
0 32
2 22
5 1
14 1 15 20 26
4 26

  

Case #1: 4 3 4
Case #2: 4
  

• After the 1st modification, A is [10, 13, 3, 7]. The subinterval (0, 3) has xor-sum 10 xor 13 xor 3 xor 7 = 3. In binary, the xor-sum is 11₂, which has an even number of 1 bits, so the subinterval is xor-even. This is the largest subinterval possible, so the answer is 4.
• After the 2nd modification, A is [32, 13, 3, 7]. The largest xor-even subinterval is (0, 2), which has xor-sum 32 xor 13 xor 3 = 46. In binary, this is 101110₂.
• After the 3rd modification, A is [32, 13, 22, 7]. The largest xor-even subinterval is (0, 3) again, which has xor-sum 32 xor 13 xor 22 xor 7 = 60. In binary, this is 111100₂.