시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
40 초 (추가 시간 없음) | 1024 MB | 3 | 3 | 3 | 100.000% |
Steven has an array of N non-negative integers. The i-th integer (indexed starting from 0) in the array is Ai.
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 AL, AL+1, ..., AR-1, AR. The xor-sum of this subinterval is AL xor AL+1 xor ... xor AR-1 xor AR, 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 Pi-th (indexed from 0) element to Vi. Steven would like to know, what is the size of the xor-even subinterval of A with the most elements after each modification?
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 Ai indicating the i-th integer in Steven's array.
Then, Q lines follow, describing the modifications. The i-th line contains Pi and Vi, The i-th modification changes the Pi-th element to Vi. indicating that the i-th modification changes the Pi-th (indexed from 0) element to Vi.
For each test case, output one line containing Case #x: y_1 y_2 ... y_Q
, where x
is 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.
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
In Sample Case 1, N = 4 and Q = 3.
In Sample Case 2, N = 5 and Q = 1. After the 1st modification, A is [14, 1, 15, 20, 26]. The largest xor-even subinterval is (1, 4), which has xor sum 1 xor 15 xor 20 xor 26 = 0. In binary, this is 02.
Contest > Google > Kick Start > Google Kick Start 2019 > Round D A번