\(L, R, U, D\) のうち絶対値が最大であるものに注目しましょう。

• \(|L|\) が最大の場合、\(x = L\) 上の格子点の色は全て \(L\) の偶奇によってのみ決まります。
• \(|R|\) が最大の場合、\(x = R\) 上の格子点の色は全て \(R\) の偶奇によってのみ決まります。
• \(|U|\) が最大の場合、\(y = U\) 上の格子点の色は全て \(U\) の偶奇によってのみ決まります。
• \(|D|\) が最大の場合、\(y = D\) 上の格子点の色は全て \(D\) の偶奇によってのみ決まります。

この事実を利用すると、行の数、または列の数が \(1\) 小さい問題に帰着することができます。 これを行数または列数が \(0\) になるまで繰り返すことで、この問題を \(O(R-L + D - U)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int l, r, u, d;
    cin >> l >> r >> u >> d;
    long long ans = 0;
    while(l <= r && u <= d) {
        int ma = max({abs(l), abs(r), abs(u), abs(d)});
        if(abs(l) == ma) {
            if(l % 2 == 0) {
                ans += d - u + 1;
            }
            l += 1;
        } else if(abs(r) == ma) {
            if(r % 2 == 0) {
                ans += d - u + 1;
            }
            r -= 1;
        } else if(abs(u) == ma) {
            if(u % 2 == 0) {
                ans += r - l + 1;
            }
            u += 1;
        } else {
            if(d % 2 == 0) {
                ans += r - l + 1;
            }
            d -= 1;
        }
    }
    cout << ans << endl;
    return 0;
}