ABC238E Range Sums

解説AC

問題へのリンク
公式解説

公式解説のメモ程度です。

の累積和をとおくと、与えられる情報は、

という風になり、

• との一方が分かれば、もう一方がわかる

という関係になる。 この関係をグラフ化し、とが連結ならYes。

ここまでが公式解説の内容です。
連立方程式を順に解いていくことをイメージしました。

ただ、にたどり着ければその値を求められるのは理解できますが、たどり着けないところも何か求める手段がありそうな気がして少し腑に落ちないところがあります。

話は変わりますが、この問題は、Xが実際の値が与えられた時に

• からへのコストXの有向辺
• からへのコスト-Xの有向辺

とすれば、実際にを求めることもできそうです。
また、このように考えると、牛ゲーの特殊バージョンと考えられるような感じもします。

別解として、以下のリンクのように吐き出し法で解かれている方がおり、公式解説より私的には納得できました。