The editorial to the first problem hasn’t been released yet , so here we go
Observations: -
1)If the xor of all the numbers in array is ‘x’, and ‘x’ is a xor-even-bits number, answer is ‘n’.
2)Say ‘m’ is the xor of full array , now how to handle updates?
If a[pi]=vi, do : m=m^a[pi](previous value)^vi(new value)
3)Again, if ‘m’ is xor-even number, output ‘n’ else , do this : -
4)If you observe carefully:- if each number in the array has even number of bits, then their xor will also have even number of bits and answer to the query will be ‘n’ .
5)If some numbers have odd bits and some have even number of bits, then the longest sub-array will always be a prefix or suffix.
Example : -
0 2 84 4 5 .
Answer is 3(0,2,84)
6)We know that ‘m’ is not a number with even number of bits as of now. It has odd number of bits.So if you remove a number from the end of the array which has even number of bits, ‘m’ will still be a number with odd number of bits…So unless, you find a number with odd number bits from the end or start, you need to keep removing elements
7)In this case :- 0,2,84,4,5 , m(xor of full array)= 87 which has odd number of bits.
Now, remove, ‘5’ which has even number of bits, and now m=82(which still has odd number of bits )
.
.
.
Now, remove, ‘4’ which has odd number of bits…the array looks like this now :- 0 , 2 , 84 .
and m=86(which has even number of bits)…
8)So the solution is , remove a prefix or suffix of array till you find the first odd(bits) element… and that’s your answer
9)Now , a question might arise, why does removing an odd element makes ‘m’ an even bits number ? You can try many examples and you’ll always find that it always true!!!…I leave the proving part up-to you (it is easy as well!!)
10)You can keep track of all the odd elements using a map.
If you have different solution to this problem, you may share int the comments
Link to my solution for full points:- TrGEAY - Online C++0x Compiler & Debugging Tool - Ideone.com