By considering the “prefix XOR sums,” we can rephrase the operation as follows:

• Choose \(i\) such that \(S_i \neq S_{i+1}\) and replace \(S_i\) with \(S_{i+1}\).

Then, we can see that we should match \(S_i\) with \(T_i\) for \(i=1,2,\cdots\) in this order. (By observing the operation, we can see that dealing with the greater \(i\) earlier is pointless.) To match them, we should look for the smallest \(j\) such that \(S_j=T_i\) (\(j \geq i\)) and propagate \(S_j\) in this way: \(S_j \rightarrow S_{j-1}\rightarrow S_{j-2}\rightarrow \cdots \rightarrow S_i\).

It takes \(O(N^2)\) time in the worst case to do this process naively. However, by memorizing that the process has made \(S_i, S_{i+1}, \cdots, S_j\) equal, we can compute the number of operations in \(O(N)\) time.