CF1381A2 Prefix Flip (Hard Version)

This is the hard version of the problem. The difference between the versions is the constraint on $ n $ and the required number of operations. You can make hacks only if all versions of the problem are solved. There are two binary strings $ a $ and $ b $ of length $ n $ (a binary string is a string consisting of symbols $ 0 $ and $ 1 $ ). In an operation, you select a prefix of $ a $ , and simultaneously invert the bits in the prefix ( $ 0 $ changes to $ 1 $ and $ 1 $ changes to $ 0 $ ) and reverse the order of the bits in the prefix. For example, if $ a=001011 $ and you select the prefix of length $ 3 $ , it becomes $ 011011 $ . Then if you select the entire string, it becomes $ 001001 $ . Your task is to transform the string $ a $ into $ b $ in at most $ 2n $ operations. It can be proved that it is always possible.

N/A

N/A

In the first test case, we have $ 01\to 11\to 00\to 10 $ . In the second test case, we have $ 01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100 $ . In the third test case, the strings are already the same. Another solution is to flip the prefix of length $ 2 $ , which will leave $ a $ unchanged.