ABC 401-500/ABC434D - Clouds - 競技プログラミング用 知識集積所

---

問題

ABC434D

必要知識

B以下レベルの内容は省略

• 二次元imos法※
• 二次元累積和※（別解なら不要）

考え方

基本的な発想として、各雲について、「雲が1つもないマス数+雲が自分しかいないマス数」を求めればよい。
ということで、まずは、各マスの雲の数を求めたい。
しかし、愚直に全範囲1ずつ足していては間に合わない。
そこで、二次元imos法※で高速化して求めることで、雲が0個、1個、であるマスの数はすぐにわかる。

難しいのはここからで、1つしか雲がないマスそれぞれについて、それが何番の雲なのかを判定し、雲ごとにマス数を合計しなければならない。
ここは少し視点を変えて、雲ごとに、自分の範囲に1つしか雲がないマスの数を数えることにする。

まず、雲が1つしかないところは全部1、残りは0とした二次元vector※を用意する。
（雲の個数をカウントしたものを使いまわしてよい）
各雲について、長方形領域の合計値を出せば、それが自分しかいないマスの数である。
これは二次元累積和※を用いて出すことができる。
これなら、全マス数回ずつ取り扱うだけなので、計算量も間に合う。

二次元imos法※のために右と下を、二次元累積和※のために左と上を、1マス余計に確保しておくと楽ではあるが、1足し忘れたり引き忘れたりというリスクも上がる。
どちらの大変さを取るかはお好みで。

解答例

解答例

注意点

別解

雲の個数をカウントするときに、範囲に1ではなくN+iを足しておく。（iは0-indexでの雲番号）
すると、二次元imos法※後の値について、

• 値が0なら、雲は0個
• 値がN以上2N未満なら、雲は1個で、その値-Nが雲の番号
• 値が2N以上なら、雲は2個以上

とでき、後半の処理がまるごと不要になる。
解答例