Consider a subproblem where \(L=D=0\) (and \(R, U\geq0\)). We want to count the number of black lattice points \((x, y)\) for which \(0\leq x\leq R\) and \(0\leq y\leq U\).

We assume \(R\leq U\) without loss of generality. The case \(R\gt U\) can be treated similarly by symmetry.

Furthermore, we divide the subproblem into two cases: \(0\leq y\leq R\) and \(R\lt y\leq U\).

For \(0\leq y\leq R\), a lattice point \((x, y)\) is black if \(\max(x,y)\) is even.

For an even number \(k\) where \(0\leq k\leq R\), lattice points with \(\max(x, y)=k\) satisfy either \(x=k\) or \(y=k\).

• If \(x=k\), then \(y\) can take \(k+1\) possible values from \(0\) to \(k\), so there are \(k+1\) lattice points.
• Similarly, there are \(k+1\) lattice points if \(y=k\).

Subtracting the overlap at \((k, k)\) gives a total of \(2k+1\).

Let \(p\) be the greatest even number at most \(R\). The number of black lattice points is the sum of the number of points corresponding to \(k\in\{0, 2, \dots, p\}\).

Since there are \(\frac{p}2+1\) possible values of \(k\), the total number of black lattice points can be written as the arithmetic series

\[ \begin{aligned} &\quad(2\cdot0+1)+(2\cdot2+1)+\dots+(2\cdot p+1) \\ &=\frac{(\frac{p}2+1)(2p+2)}2 \\ &=\left(\frac{p}2+1\right)(p+1). \end{aligned} \]

For \(R\lt y\leq U\), since \(0\leq x\leq R\lt y\), the color of a lattice point depends only on the parity of \(y=\max(x, y)\).

Since there are \(R+1\) lattice points for each value of \(y\), the number of black lattice points is \(q(R+1)\) where \(q\) is the number of even numbers in the interval \((R, U]\).

Thus, we obtain a formula for the number of black lattice points in the subproblem where \(L=D=0\).

We can reduce the original problem to the above subproblem via symmetry and the inclusion-exclusion principle. The time complexity is \(O(1)\).

Sample Code (Python)