Nyctophobia

類題です 類題その2です

この解説では操作 $1$ のことを「操作」、操作 $2$ のことを「移動」と呼びます。

便宜上マス $0,N+1$ を白であると見做し、$d_i=($マス $i$ とマス $i+1$ の色が異なれば $1$、同じなら $0)$ と定義します。すると、各操作は $d_{L_i}$ と $d_{R_i+1}$ を01反転することに言い換えられます。また、マス $i$ からマス $i+1$ に移動するためには $d_i=0$ が必要だと分かります。

開始時点ではマス $1$ で操作を行うことしかできません。よって $1 \lt L_1$ なら不可能であり、可能なら必ずマス $1$ での操作が行われます。

Vil君のいるマスとそれ以前のマスは全て白であると仮定した場合のマス $i\ (1 \lt i)$での操作について考えます。操作区間がVil君のいるマスを含む$(L_i \le i \le R_i)$場合、操作後にVil君のいるマスが黒になり移動ができなくなるため、この操作は無意味です。操作区間がVil君のいるマス以前である$(R_i \lt i)$場合、この操作が後にVil君のいるマス以降への移動を可能にすることに寄与するとすれば、その過程で操作区間がVil君のいるマスを含む操作を行うことになるためこちらも無意味です。また、これにより仮定が常に維持されます。

開始時点では $d_0=d_{N+1}=1$ でその他は $0$ であるため、マス $N$ に到達するためには(マス $1$ での操作を含む)意味のある操作をいくつか行なって $d_0,d_{N+1}$ を奇数回、その他を偶数回反転させればよいことが分かります。これは、頂点 $1,2,\dots,N+1$ からなる空グラフに $i=1$ または $i \lt L_i$ であるような $i$ のみについて無向辺$(L_i,R_i+1)$ を張った時に頂点 $1$ から頂点 $N+1$ までのパスが存在するかどうかを見れば判定可能です。また、最小回数はこのときの頂点 $1$ から頂点 $N+1$ までの距離に等しくなります。以上でこの問題を解くことができました。計算量は $O(N)$ です。