ABC058D/ARC071B 井井井を解きました

🍣

これを解きました：ABC058D/ARC071B 井井井

全部の長方形を計算するのはもちろん間に合わない。

結局、長方形の面積を出すときに、縦の長さを全部書き出して、横の長さを全部書き出して掛けるのだから、「縦の長さを全部足したもの」×「横の長さを全部足したもの」とやっても出せる。

横の長さを全部足したものは、例えば、x(i) から x(i+1) の辺が選ばれる場合を考えると、左がi以下、右がi+1以上を選んだ場合なので、こうなる場合の数は掛け算で求まる。この回数だけ x(i+1)-x(i) が足されるので、この横幅を掛ければいい。あとはこれをiについて足せば、「横の長さを全部足したもの」になる。

縦も同じようにして、あとは掛ければ求められる。

はじめ、NとMが同じだと勘違いしていてバグらせてしまった。