黒く塗られるのは $k$ が偶数のときだから、 $k = 0, 2, 4, \cdots, 2m \: (m \text{は整数})$ のときの点の数を足し合わせればよい。これは初項 $1$ 、公差 $4$ 、最終項 $4m + 1$ 、項数 $m+1$ の等差数列の和であるから、この領域の黒い格子点の個数を $c_1$ とすると、

c_1 = \dfrac{(1 + 4m+1)(m+1)}{2} = (m+1)(2m+1)

となるが、これは $m$ の偶奇によって以下のように場合分けが発生する。

c_1 = \begin{cases} \left( \dfrac{X}{2} + 1 \right)(X + 1) = \dfrac{(X+1)(X+2)}{2} & \quad (X \text{が偶数}) \\ \left( \dfrac{X-1}{2} + 1 \right) X = \dfrac{X(X+1)}{2} & \quad (X \text{が奇数}) \end{cases}

長方形領域の計算

この領域では常に $\max(x, y) = y$ が成り立つから、 $y$ 座標が偶数の格子点はすべて黒である。

$X \leq y \leq Y$ の範囲の偶数の個数は、

\left( \left\lfloor \dfrac{Y}{2} \right\rfloor + 1 \right) - \left( \left\lfloor \dfrac{X}{2} \right\rfloor + 1 \right) = \left\lfloor \dfrac{Y}{2} \right\rfloor - \left\lfloor \dfrac{X}{2} \right\rfloor

となる。

横方向には点が $X + 1$ 個あるから、これを掛けることによって、この領域の黒い格子点の個数を $c_2$ は、

c_2 = \left( \left\lfloor \dfrac{Y}{2} \right\rfloor - \left\lfloor \dfrac{X}{2} \right\rfloor \right)(X+1)

と計算できる。

以上により、 $f(X, Y) = c_1 + c_2$ と求めることができた。

与えられた矩形領域の正領域への分割・移動

与えられる矩形領域は負の範囲を含むこともあるが、 $f(X, Y)$ を使うためには正領域に移さなければならない。

ここで、数直線上の区間 $[L, R]$ を、絶対値をとった $0$ 以上の区間に分割することを考える。

$0 \leq L \leq R$ : そのまま $[L, R]$ とする。
$L \leq R < 0$ : 区間全体を折り返して $[-R, -L]$ とする。
$L < 0 \leq R$ : $[L, -1] + [0, R]$ に分けて考え、前者を折り返して $[1, -L], [0, R]$ とする。

これを $x$ 軸 $[l, r]$ と $y$ 軸 $[d, u]$ それぞれについて処理すればよい。

包除原理を利用した正領域の矩形領域内の黒い格子点数の計算

最後に、 $0 \leq l \leq x \leq r, \, 0 \leq d \leq y \leq u$ の正領域の矩形領域が与えられたときに、その中の黒い格子点の個数を求める。

これは、包除原理の要領で、 $f(X, Y)$ を用いて以下のように計算できる。

f(r, u) - f(l - 1, u) - f(r, d - 1) + f(l - 1, d - 1)

以上より、全体としては定数時間でこの問題を解くことができる。

詳細は実装例も参照のこと。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.using ll = long long;
7.using Pair_ll = pair<ll, ll>;
8. 
9.// ======================================== //
10. 
11.ll f(ll x, ll y)
12.{
13.    if (y < x)
14.        swap(x, y);
15. 
16.    ll res = 0;
17.    if (x % 2 == 0)
18.        res += (x + 1) * (x + 2) / 2;
19.    else
20.        res += x * (x + 1) / 2;
21. 
22.    res += (y / 2 - x / 2) * (x + 1);
23.    return res;
24.}
25. 
26.int main()
27.{
28.    ll L, R, D, U;
29.    cin >> L >> R >> D >> U;
30. 
31.    auto calc = [](ll l, ll r, ll d, ll u) -> ll
32.    {
33.        return f(r, u) - f(l - 1, u) - f(r, d - 1) + f(l - 1, d - 1);
34.    };
35. 
36.    auto convert_interval = [](ll l, ll r) -> vector<Pair_ll>
37.    {
38.        vector<Pair_ll> res;
39.        if (r >= 0)
40.            res.push_back({max(0LL, l), r});
41.        if (l < 0)
42.            res.push_back({max(1LL, -r), -l});
43. 
44.        return res;
45.    };
46. 
47.    vector<Pair_ll> lr = convert_interval(L, R);
48.    vector<Pair_ll> du = convert_interval(D, U);
49. 
50.    ll ans = 0;
51.    for (auto &&[l, r] : lr)
52.    {
53.        for (auto &&[d, u] : du)
54.        {
55.            ans += calc(l, r, d, u);
56.        }
57.    }
58. 
59.    cout << ans << endl;
60. 
61.    return 0;
62.}