AtCoder Grand Contest 015 C 「Nuske vs Phantom Thnook」

問題文

C - Nuske vs Phantom Thnook

 

長方形領域を横に伸ばしていくとき、領域内の連結成分の個数がどのように変化するかを調べると、新しく追加された列にある連結成分の個数だけ増えて、新しく追加された列にある青マスのうち、その左も青マスであるものの個数だけ減ることがわかる。具体例を以下に示す。

f:id:Div9851P:20190106110054p:plain

f:id:Div9851P:20190106110320p:plain

f:id:Div9851P:20190106110404p:plain

f:id:Div9851P:20190106110520p:plain

f:id:Div9851P:20190106110543p:plain

ただし、これは「任意の二つの青マスa,bについて、青マスだけをたどってaからbまで行くルートは高々1通りしかない」、つまり青マスの閉路がないという制約がないと成り立たない。例えば以下のような例で上手くいかない。

f:id:Div9851P:20190106112034p:plain

ではある列に連結成分が何個あるかはどう数えればいいのかというと、「その列にある青マスの数」-「その列にある青マスのうち上も青マスであるものの数」で求まることがわかる。結局、ある長方形領域にある連結成分の個数は「その領域にある青マスの数」-「その領域にある青マスのうち左も青マスであるものの数」-「その領域にある青マスのうち上も青マスであるものの数」で求まることがわかったので、あとは累積和をとって高速に計算してやればいい。

 

制約的に前計算しておいて各クエリにO(1)で答える奴だろう、ということで累積和で上手くいかないかな?と読んだのが功を奏した。差分に注目するのも重要。