Editorial for DMOPC '22 Contest 5 P3 - Sorted XOR
Submitting an official solution before solving the problem yourself is a bannable offence.
Performing an operation can change the prefix bitwise XOR to any value. Each time we must perform an operation, we consider which bits should be set in the prefix bitwise XOR. We can always a flip a really large bit to make the XOR value greater than the previous one. Thus, we just need to consider the bits up to the highest bit that contains.
Run a naive which represents the minimum number of operations you need to perform to make nondecreasing for the first elements and with a current prefix bitwise XOR of .
Maintain the prefix bitwise XOR as an array of size whose values can be , , or , where represents bits which are arbitrary. Initially, all bits are . Whenever you perform an operation, all bits become arbitrary. The only time the prefix bitwise XOR would decrease is when the highest bit of is set in the running bitwise XOR, so an operation must be performed. Loop through the array and perform an operation if necessary. Otherwise, set the highest bit, then loop through the bits and XOR each bit of with each known corresponding bit in . The arbitrary bits remain unknown, since they could still be either or .