問題

https://codeforces.com/contest/1080/problem/C

市松模様の $n$ 行 $m$ 列の表が与えられる。 $(x_1, y_1), (x_2, y_2)$ で囲まれる長方形を中をまずすべて白で塗りつぶす。その後 $(x_3, y_3), (x_4, y_4)$ で囲まれる長方形の中を黒で塗りつぶす。白マスと黒マスの数を求めよ。

制約

$1 \le n,m \le 10^9$

考え方

$n \times m$ の表に含まれる黒と白のマスの数はすぐにわかる。奇数行目は白のマスが $\displaystyle \lceil \frac{m}{2} \rceil$ つ存在し、偶数行目は $\displaystyle \frac{m}{2}$ つ存在することがわかる。よって $n$ 行あるとき $\displaystyle \lceil \frac{m}{2} \rceil \times \lceil \frac{n}{2} \rceil + \frac{m}{2} \times \frac{n}{2}$ つ白マスがあることがわかる。黒マスは $n \times m$ から白マスの数を除くことで求められる。

次に点 $(a, b), (c, d)$ で囲まれる長方形に含まれる白マスの数と黒マスの数を求めたい。これを求めることができれば、題意で与えられている操作は

(1)黒マスから白マスになる数

(2)白マスから黒マスになる数

(3)重なる範囲についてもともと黒マスだったマスを黒くする数

の $3$ つの操作をすることで解を得ることができる。

点 $(a, b), (c, d)$ で囲まれる長方形に含まれる黒マスと白マスはどのように求められるか。黒マスは白マスの結果から簡単に求められるので、白マスの数を求めることにする。これは $2$ 変数の包除みたいなイメージで

$(1, 1), (c, d)$ の長方形に含まれる白マスの数 - $(a-1, d), (c, d)$ の長方形に含まれる白マスの数 - $(c, b-1), (c, d)$ の長方形に含まれる白マスの数 + $(1, 1), (a-1, b-1)$ の長方形に含まれる白マスの数

として求めることができる！

これで (1), (2) を求めることができた。(3) について、 $2$ つの長方形が重なる長方形の範囲は $(max(x_1, x_3), max(y_1, y_3)), (min(x_2, x_4), min(y_2, y_4))$ として求めることができる。よってこの重なる長方形の範囲に含まれる黒マスの数を数えれば良い。