The distance defined in the Problem Statement is invariant under transformation, and the distance between \((X,Y)\) and \((0,0)\) is \(\max(|X|,|Y|,|X-Y|)\). By a coordinate transformation \((X,Y)\mapsto(X,Y,X-Y)\), the Chebyshev distance after the conversion gives the same distance as the original.

Therefore, the problem on the coordinates after conversion is as follows: “how many sets \(T\) fit in a \(D\times D\times D\)?” This problem can be solved as follows.

We count the conforming sets by grouping them by the minimum value of each component of the points. The number of sets where the minimum value of each component is \(X\), \(Y\), and \(Z\) can be obtained by dividing the points in \([X,X+D]\times[Y,Y+D]\times[Z,Z+D]\) into eight groups, depending on whether the \(x\) coordinate is \(X\) or not, the \(y\) coordinate is \(Y\) or not, and the \(z\) coordinate is \(Z\) or not. For each fixed \(X\) and \(Y\), we can find this by iterating through \(Z\) and managing the deltas in a total of \(O(N)\) time. Therefore, the problem can be solved in a total of \(O(N)\) time.

writer’s solution (C++)
writer’s solution (Python)