ちょっと悩んでしまったが、良い感じにきれいに解けた。

解法

一般に、 $X _ {i} \lt X _ {i+1} (0 \le i \lt N-1)$ 、 $Y _ {j} \lt Y _ {j+1} (0 \le j \lt M-1)$ とする。

$X _ {i}, X _ {i+1} (0 \le i \lt N-1), Y _ {j}, Y _ {j+1} (0 \le j \lt M-1)$ によって構成される格子の1マスに注目して、これがいくつの長方形に含まれるかを考えると、これは

$(i+1) * (N - i - 1) * (j+1) * (M - j - 1)$

となる。(縦の辺については、左側は $i+1$ 通り、右側は $N - i - 1$ 通り、横の辺については、上側は $M - j - 1$ 通り、下側は $j+1$ 通りあるので、上のような式になる)

よって、求めるべき答えは、

$\sum _ {i = 0} ^ {N- 2} {\sum _ {j = 0} ^ {M - 2} (X _ {i+1} - X _ {i})(Y _ {j+1} - Y _ {j})(i+1)(N - i - 1)(j+1)(M - j - 1)}$

となる。 $i, j$ は独立しているので、簡単に式変形できる。

$(\sum _ {i = 0} ^ {N-2} {(X _ {i+1} - X _ {i})(i+1)(N - i - 1)})(\sum _ {j = 0} ^ {M-2} {(Y _ {j+1} - Y _ {j})(j+1)(M - j - 1)}$

左右のカッコの中身は見ての通り、愚直に計算することでそれぞれ $O(N), O(M)$ で計算できるため、全体で $O(N + M)$ で答えを出すことができる。

実装例は以下の通り。

競プロ備忘録