累積 xor を取ると，問題の操作は次のように言い換えられます．

• \(S_i \neq S_{i+1}\) なる \(i\) を選び，\(S_i\) を \(S_{i+1}\) で置き換える．

すると，この問題は，\(i=1,2,\cdots\) について，この順に，\(S_i\) を \(T_i\) に一致させて行けばよいとわかります．（操作の様子から，先に大きい \(i\) で \(S_i\) と \(T_i\) を一致させる意味がないとわかります）一致させるためには，\(S_j=T_i\) (\(j \geq i\)) となる最小の \(j\) を探し，\(S_j \rightarrow S_{j-1}\rightarrow S_{j-2}\rightarrow \cdots \rightarrow S_i\) と \(S_j\) を伝搬させればよいです．

この操作を愚直にやると最悪 \(O(N^2)\) 時間かかりますが，上の操作後 \(S_i,S_{i+1},\cdots,S_j\) がすべて同じになっているという情報を持つことで，\(O(N)\) 時間で操作回数が計算できます．