2011JOI本選1 惑星探査 解説

問題リンク

解説

調べなければいけない長方形が多いので、それぞれの長方形について高速にクエリを処理する必要があります。

これは、二次元累積和を使って、それぞれの種類のブロックが、1頂点を左上の端などに固定した長方形 通りの中にいくつかあるかを高速に求めることができれば、長方形の足し引きによってどの長方形に対しても答えることができます。

二次元累積和について検索すればわかりやすいと思います。