B - Flip Digits Editorial by maroonrk


累積 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)\) 時間で操作回数が計算できます.

posted:
last update: