2011JOI春合宿1-1 Banner 解説

問題リンク

解説

求めるべき長方形がどのような形をしているか考えてみます。 題意より、求める長方形は3頂点が異なる色で、残りの1頂点は残りのどれかと同じ色です。

このような長方形には、3頂点が異なる色になるL字型の部分が必ず2つ含まれています。 よって、このような部分の個数を数えて2で割った商を答えればよいです。

このような部分は、L字の真ん中の頂点を決めれば、縦と横にそれぞれの色の頂点がいくつあるか数えれば良いです。 これは累積和を先に取っておけば計算できます。